Odd. Just noticed this now. Upgraded to 3.1 yesterday, if it means anything.
Category links won’t work:
Though, tags and permalinks still work fine:
I tried changing the category slug back to ‘category’. Still didn’t work. Any ideas?