Okay, I must have been reading part of an answer then because
I remembered colored cells. Perhaps you are printing in draft mode
since it will only print 1/4 of the dots it wouldn't do a good job of printing
gridlines so they are just ignored..
Try removing all color within cells, and removing all borders
Select all cells Ctrl+A (or in Excel 2003 Ctrl+Shift+SpaceBar
-- Borders drop down upper left corner is no borders
-- Fill color (paint bucket), top is no fill color
Check with Print Preview
Try printing with all borders involved.
.
http://www.mvps.org/dmcritchie/excel/gridline.htm
Select all cells Ctrl+A (or Excel 2003 same as above)
Format, cells, borders
choose a line, choose automatic, click on both inside and outside borders
Check with Print Preview