I've actually had the same problem with a couple of my users. I've just been putting 2003 publisher back on their computer just to get by for the time being.
The funny part is that it didn't start happening until SP1 was applied, actually. Another Service Pack that breaks things instead of fixing them I guess.