ib

I used to have a similar problem, this is how i fixed it:

1. Follow Step 2 of http://codex.wordpress.org/Using_Permalinks#Fixing_.28.htaccess.29_Generation_Issues

2. Delete your .htaccess
3. Update the permalink structure in CP.

Hope it helps