I have exactly the same problem here with FC 3. Installing the RPMs with the --nodeps flag only result in a not-working VLC...
The included libcdio RPM installs fine though, but that doesn't seem to include 'libcdio.so.0' and those other missing things.
EDIT: Read another post from HellSpawn:
yum localinstall videolan-client-0.8.1-1.1.fc3.rf.x86_64.rpm
Might try that to install the deps