I've had the media library enabled since it was introduced, but it has only been in the last few versions where browsing media has become unbearably slow. I did make one change to the setup, switching from a wireless connection to a wired one (to speed up streaming of HD media files), however I wouldn't expect that to slow down browsing.
On a similar note, last night I was browsing a directory for a season of a TV show which had around 50 episodes in it, and I kept receiving "There are no titles" from the PS3 after about 3-4 minutes of it trying to load the directory listing. Tried disabling the media library, resetting the media library, and deleting the media library, but nothing worked. I had to break the list in half to view it successfully. Again I had never seen this type of issue with previous versions, I'm thinking pre-1.04 but that would be a total guess on my part.
I may try reverting to a previous version in the next couple of days if I have time, and if that fails I may install TVersity or similar to try and rule out the PS3 as the culprit.