WordPress category gives 404 after moving to a different domain

I just moved a site from one domain to another and now category links are all 404. I have flushed the rewrite rules, recreated the .htaccess file but still it throws up 404.

Weird thing is that if I delete .htaccess file, then the posts are still accessible by domain.com/postname/ and when I save permalinks, then it is created there. So can it be the case it is using some other .htaccess file? Possibly some fallback that I am not aware of?

Tag pages work fine. Also I am using a custom slug for category “cat” and not the default “category” but reverting to the default doesn’t solve anything. Any clues?

Edit: I saw Ipstenu’s sticky and found that Advanced Permalinks are known to have a problem with WP 3.1, so I disabled it and recreated by permalinks but still no joy. What did I miss?