I have been having this same problem on my Roku 1000.
Playlists have been working well but no other browse of artist or album.
After reading this thread, I thought I would try and figure this out. I tried my playlists that normally work, but one of the random 2 hour playlist failed intermitenly. (this is the first time I noticed this.) This gave me an idea. I thought I could recreate this with the playlist instead of remaking a library.
So, I put in a few hundred titles and it worked. I put in a few hundred more and it failed. Next I took out the first few hundred to see if I had narrowed it down to the second few hundred, but it worked. I tried this a few times, but it seemed to be more related to the number than the actual titles or artists.
So, to try out the number theory, I put one song in and tried. This worked. Next, I copied the same song 100 times in my playlist, and it also worked. Next I copied it so that I had 300 and it failed. Next I backed off to 275 copies and it worked. I could not always get it to fail on the same number, but it would fail right around the 300 mark.
I think this has to do with the number of charachters in the total length. It is not related to special charachters.
Hope this helps, let me know if there is anything else I can do to help debug.
I really want to get this to work, although I want my iPod photo to stop skipping long names first!
Thanks -Dons