In my case with Suse 10.1 and vlc completely compiled myself (with most of the libraries) it plays very fine without any skipping etc. and the music quality is also very good, much better than usual with webradio. It is really perfect. At the moment there is "Pictures of an exhibition" one of the few classic things I recognize.
I would look in your firewall and security configuration with Fedora, in particular if there are not some netfilter rules which block when there are two many incoming packages or something like this, even though the html protocol should work very fine, even behind a NAT routeur (which is just my case).
The problem with Fedora is that there are many subtle security configurations and for a normal Linux user who knows Linux quite well, many of these things come as a surprise, for example if even root cannot do everything due to some special security options. At occasion I have been very annoyed with Fedora due to this, especially the Sel-Linux thing (?). You may try to reduce the general level of security settings.
Apart from this you may also look at certain caching options (in the preference menu of vlc), may be increasing the caching time for streaming etc.
They may also be a particular problem with a (partly) broken or too old library (maybe faad2 which must decode the AAC mp4a for vlc ?) and which does not appear in my case, because I compiled everything myself with quite recent versions. However, such type of problems may be very difficult to pinpoint.