Many people have reported permalinks not working after upgrading to 2.6. In all cases, these people have permalink structures that contain "index.php". This is a bug, detailed here: http://trac.wordpress.org/ticket/7306
Temporary fixes (any one of these works):
1. If you're using Linux/Apache on your webserver, you don't really need the index.php anyway. Try removing it. The index.php thing was only meant for IIS servers, which don't support mod_rewrite.
2. If you need/want the index.php to be there, then on the Settings->Permalinks screen, add some values in for the category and tag bases. The words "category" and "tag" will do just fine. As long as they are not blank, this should work around the bug.
3. (For advanced users only) If you want to patch the problem yourself, there is a fix available in trac ticket 7306.
The upcoming release of WordPress 2.6.1 will correct this issue.