I used Avidemux 2.5.2 that comes with Ubuntu Lucid without problem. Then I found the "bleed" repository https://launchpad.net/~lucid-bleed/+archive/ppa that offers Avidemux 2.5.4-0ubuntu5~ppa1~lucid1 as of december 2010.
When using that version 2.5.4, I am no longer able to control the bitrate of my x264 videos. Whether I use "Two Pass - Video Size" or "Single Pass - Bitrate (Average)", the program seems to constantly use quantizer 19.
Looking for an explanation, I first found this forum post that seems to be very similar to what I saw: http://avidemux.org/admForum/viewtopic.php?id=8822
I'm back to Lucid's 2.5.2 for now.