I'm having exactly the same problem [with a bit of a difference].
I was able to copy some MP3s as a test to a new folder ['iTunes'] on the Share, and checked that this was enabled under Extensions > Media Server [which it was].
This worked fine on two machines: I could see the Linkstation in iTunes [version 9] and could play the tracks.
However when I turned the Linkstation off and on another day, the tracks were listed, but wouldn't play.
I've since upgraded to iTunes 10 and created a new folder ['MP3'] on the Share, and copied all my MP3s there.
I went through the same process as before, pointing the Media Server at the new folder and check that it was enabled.
Which worked fine - I was able to play the MP3s through iTunes.
However... I left the Linkstation on overnight, tried to access the shared [which is now calling itself 'untitled playlist' until you select it and then it remembers its name] - and it is empty!
This is however working fine on my iBook G4 under OSX 10.3 running iTunes 7.
I bought this device for ease [and due to its good reviews] and can no way be bothered to keep either logging in and refreshing the server or copying the MP3s each time I want to access it. I don't understand why the setup is only temporary.
Maybe dropping back a version of iTunes might be a fix?
Ben