It's easy enough to convince Nautilus to launch VLC, but VLC fails to find the multimedia files. This only happens if the SAMBA share is mounted by Nautilus. If I mount the SAMBA share manually from the command line, VLC finds the files just fine.
The problem is that Nautilus points VLC to a non-existent path that lives on the Gnome virtual file system (GVFS).
The fix is to install the GVFS FUSE daemon, which, for some reason, is not installed by default:
aptitude install gvfs-fuseadd your user account to the
fusegroup, and re-login.