My blog is http://www.topofmindblog.com
I have had this problem before, but it went away after I reinstalled WP a year back, and now it's back - suddenly. Please note that no changes were made prior.. I just realized one day when I was looking around that none of my links were working.
For example the address bar would show http://topofmindblog.com/2007/06/17/top-48-things-i-learned-from-watching-lost/
but the actual page displayed will be the home page. Same with the category as well.
From past experience and checking out the http://codex.wordpress.org/Using_Permalinks I checked if my .htaccess is at 666, then updated the permalinks. But still not working.
Weired thing is that at default Permalink STructure both the category and post links work, but when I change it back to my Pretty Permalink "Date & Name." it stops working.
Now I have not seen any problems in the forums and at a loss. I mean I can keep the Permalinks at default, but then I will lose all the outside links and as teh WP forum says "p=61" is UGLY!!