We have folders with 3000+ folders...takes about 2-3 seconds to display when browsing to the folder. This is 2009 sp4.
Which version did you say you were on? What are your server specs?
Check SPR 497977 maybe?
I was originally thinking of SPR 475001, but it was fixed in SP 3, which you are on.