Please help me convert from date to category permalink

I have a self hosted WP installation and have been posting since August 2010. Not sure why but I went with the Day and Name permalink initially. I now realize that it would be far better to go with a custom permalink using category/postname.

WP does an amazing job in seamlessly changing all of my old posts BUT that seems to break external links. For example, posts on my FB page go to a not found page on my site after making the change. Is there any way around this?

Thanks in advance!