Category troubles, 404 Error

Hi,

I recently changed my perma-link structure for my categories, from the default http://blog.com/category/categoryname to http://blog.com/categoryname
but right now i have 404 errors http://blog.com/categoryname/feed

with the previous structure it is an error http://blog.com/category/categoryname/feed

Anyone know how to resolve this issue. Running on WordPress 2.9.1, didnt work on the previous version too.

Plus the pagination doesnt work now in the categories. Goin to page 2 sends the page to 404 error page.

please help.