without recompiling the test executable (so it gets compiled against the default Ubuntu libraries/shared objects), but using the latest shared objects compiled from svn ffmpeg code cut, theora decoding does work.
Again I hope this is not only sufficient but you can consider it as definitive proof of what is happening:
default libav*.so.* from Ubuntu ==> doesn't work
latest svn cut libav*.so.* from ffmpeg website ==> does work
Again I didn't recompile the executable, just changed the shared objects.