PS3 + Mediaserver, Probleme mit shuffle-Funktion

Hallo,

hab die Fritz-Box 7270, welche bei mir als MediaServer läuft, also externe Festplatte am Router dran. Die PS3 findet diesen MediaServer auch und ich kann Bilder Musik etc. auswählen und anschauen/hören.
Das Problem bei mir ist nun die shuffle-Funktion. Also ich hab auf der externen Festplatte einen Ordner, in dem ca 4000 MP3-Dateien drin sind. Wenn ich nun bei meiner PS3 -> Mediserver -> Titel anzeigen mache, irgend ein Lied starte und shuffle aktiviere, dann shuffelt der nicht alle 4000 Lieder durch, sondern bleibt immer bei den "oberen" liedern hängen, also die mit A oder B anfangen. So als ob er den Rest garnicht kennt oder nicht nachlädt...!? Hab sowohl WLAN als auch LAN probiert, beides das gleiche Problem. Hat jemand eine Idee?