FFmpeg can do this as tgm4883 mentioned, but you will need to compile it yourself first because the repository version (as of Natty) does not include filters. Compiling FFmpeg is easy with these instructions:
HOWTO: Install and use the latest FFmpeg and x264
Example. This will rotate the video 90 degrees clockwise, encoded as H.264 video in MKV container. The audio will simply be copied (no audio re-encoding):
More info on the transpose filter can be found in with the man ffmpeg command.
ffmpeg -i input -vcodec libx264 -preset medium -crf 24 -threads 0 -vf transpose=1 -acodec copy output.mkv