Well – I ended up keeping WordPress as the blog enginebut I switched to a Linux host. I really liked my host (WebHost4Life) for Windows (ie. ASP.NET) hosting. But they dont offer Linux hosting. So to make things easier, I switched over to DreamHost. DreamHost has a fantastic feature set (basically everything you could ask for on linux and a shared hosting plan), the price is reasonable, and they set my site up within about 10 minutes from when I submitted my information. Thats excellent – other hosts take at least a few hours to do everything if not a couple of days, so Im impressed with DreamHost so far.
Anyway, the permalink structure is now working again as are the About Me/Contact Me pages. Old permalinks will break at the moment (if they have /index.php/ in there, that needs to be removed and then itll work. Id like to find a way to automatically transfer the old permalinks to the new ones, but I dont have the time to learn how to work with mod_rewrite to do the translation before sending it over to WordPress (if you happen to know how to do that and wouldnt mind letting me know, that would be awesome). I dont think there are all that many incoming links at the moment since the blog is so new – so hopefully this wont be a problem.