Since I upgraded from Ubuntu Feisty to Gutsy on my laptop, VLC has refused to run. Trying to run it from the command line yielded an impressive (!) list of errors. In doing some snooping aroung Googlespace yesterday I came across this thread over on the Ubuntu forums. The bug seems to be related to the new glib memory allocation routines but, fortunately, the fix is simply a matter of setting an environment variable before calling vlc.
For me, calling vlc in the following way fixed my problems:
I'm sure a more permanent fix is in the works.