Is there a maximum number of categories?
There's no fixed limit i'm aware of, i have one site with about 1,500 - ah, right, the categories are ok but you can't save a page with that many, so i think it's an issue with the number of inputs in the wiki edit form, and there's a php.ini setting max_input_vars which i think defaults to 1000, but you need two for each category - so try setting this to a huge number (try 5000 or 6000) and restart your web server.
Hope that helps?