Well it seems obvious that it's something in Autocad... but I'm exhausted of possibilities too.
Run me through your plotting setup, if you will.
Do you use Page Setups?
PC3's (or other variant) or standard windows plotter driver?
What about your plot style file? CTB/STB, and where are they located (meaning, local or network?)
Check the default settings for all your regular plot window stuff... shade plot, quality, all plot options, blah blah blah...
that's about all I can think of atm.