sudo apt-get remove libavcodec51
If you still have problems there might be stale libraries in here: /usr/lib/libavcodec.*. Try moving them somewhere else and see if that helps. Otherwise, send me a comment. ;)
See here for a more elegant work-around that tells the package manager we've got newer libraries available.