I had exactly the same problem when I started using MC a few weeks ago. The reason for this behaviour is that the server is streaming the content to the clients rather than the clients playing back the files as local content.
So, on the server, the media import folders are probably setup as local folders.
For example:
E:\Movies
E:\TVShows
E:\Music
What you want to do is share these folders on the server and then change the media import folders in MC options to full network UNC paths.
For example:
\\MediaServer\Movies
\\MediaServer\TVShows
\\MediaServer\Music
Then, on the client, goto 'Options --> Media Network --> Client Options' and tick the box that says "Play local file if one that matches library server file is found".
Now, because the client can see the files directly over the network it will treat them as local files and play them back as such.
Unfortunately, this will mean you having to re-import all your files but I do think this is the best way to go.
There is one other option that will not require re-importing as Matt said. That is to share the media folders on the server and then map these network shares on the client as a mapped drive. However, the mapped drive path on the client will have to match exactly the same path on the server.
So, for example, if the local path to a media file on the server is 'E:\Movies\Inception\Inception.avi' then the path on the client via the mapped drive would have to be exactly the same 'E:\Movies\Inception\Inception.avi'.
I personally havn't tried doing it this way because when I came across the problems you outlined I was still in the process of setting the system up so it was easy to change it and re-import. However, I would still say that, if you can, then the first option is the better way to go.
Just one other thing, in both examples make sure that the client machine has sufficient access privileges to the shared media folders on the server. When I first set this up the clients would show the thumbnails and details for the movies but would not play them. This was because I had not given the clients access rights to the server media folders. Once I had done that though everything plays back on all clients as though they were local files with normal rewind/forward etc.
I hope this helps
Russell