permalinks permanently moved not working for IE

I recently tried to move my site from its default URL structure to a more conventional URL structure using permalinks permanently moved. I’m primarily a Firefox user, so I was most pleased that upon initiating the plugin seeing it work perfectly. However, I hopped on both IE 6 and IE7 and it appeared that the code was broken. The content was there, but the CSS did not appear to load, and the site was a disaster (aside from the home page, which still looked fine).

Has anyone else run into this issue and do you have any advice? Changing the URLs is the last step in our on site SEO and this is pretty frustrating.

Thanks.