Ok... Did a quick test on my backup server (P2 300, 128M ram)

Ripped an ~5 minute track, fed it to lame with -m a -q 2 -h -v -V 2 -b 96 -k as the options...

Encoding at .6599x realtime... so, about 8 minutes.

This is with the most recent version of lame, on a Debian linux box.

Gotta say something is up with your setup...