@Davex
:: MOST IMPORTANT STEP!!! Went to http://YOUR BLOG NAME/blog/wp-admin/options-permalink.php and made sure DEFAULT is chose under COMMON SETTINGS
Yes but some people prefer, and have been using custom permalinks. Changing this permalink back to default creates a whole lot of broken links on other websites that link to your posts or pages using the permalink. I noticed this same problem occurred on my blog after upgrading to 2.6.3
The previous steps you mention are the proper steps to take when upgrading. That last step may be a solution to this problem, but is not the solution. I somehow get the feeling there is some sort of bug in WP 2.6.3 with the permalinks.
This is however a completely different problem than the one this post started out with.