Rewriting — Baffling situation

I am troubleshooting something strange here:

If I setup my permalinks like this:
/%postname%/%category%/ everything works

but if I set it up the way I want it like this:
/%category%/%postname%/

it doesn’t work and can’t find them??

Now keep in mind when I first installed this the second way worked just fine, then I re-organized the posts and categories and it doesn’t work.