Definitely sounds like a RMW issue...
What are you driving with the pins? LEDs without series resistor or something capacitive?
I'm surprised you say that Charles workaround with the Shadow variable doesn't work though. Which PIC are you using? If it has LATx registers try using those instead of PORTx when setting your outputs.

/Henrik.