Just to let everyone know.
1. I added the word CATEGORY to the category base and TAG to the Tag based and saved it using the default settings.
2. Then I choose my permalink settings /index.php/mypostsdontwork and everything is in working order.
This is on a windows windows btw. It might just solve others problems as well!
I did what OTTO said to do here http://wordpress.org/support/topic/189041?replies=11 while crossing my fingers and it paid off! Thanks!