Ok, I did this:

Close Excel and
Windows Start Button|Run
excel /unregserver
then
Windows Start Button|Run
excel /regserver

Now the Excel Paste Special menu comes up if I use a single instance of
Excel. However, it is imperative I get the paste special menu to work
properly with multiple instances of Excel. I do a TON of work over a
network. Opening the files back and forth would be a pain.

Thanks!!!

Andrew