PageMaker and InDesign are notorious for formatting problems like this, just as MS Publisher absolutely never gets the fonts right on a different computer.
Have you ever tried Scribus
scribus.net | Scribus Open Source Desktop Publishing It's open source, so it's completely free. It's also completely cross platform (Windows, Mac, and Linux)
Try printing your doc through Scribus (you'll have to export your InDesign to a .PS file, then Import and check your document before you export it to a PDF and print.) If it doesn't print correctly from here it never will, and its a machine or driver problem
Scribus' only mission in life is to be a stellar Desktop Publishing application - it does not print directly, but outputs a very high quality .PDF file which can be printed locally or sent to any print shop without a problem (remember to embed the fonts) I've done several projects with it - it's easy to learn and use, has a great support community, and it absolutely free. I've also had absolutely no problems creating a document on my Linux home computer, editing it on the Windows XP box at the charity I work with, and tweaking it again on an OS 10.4 mac at the print shop running it for me.