I've had the same issue with Audacity 1.2.6 and 1.3.7 beta versions.. "Could not open MP3 encoding library"... At first I thought that this is a bug of audacity and there is nothing I can do but after a
little research I made it work finally..

so let me tell you my steps:
I've downloaded lame mp3 encoder not from
http://lame.buanzo.com.ar/ but from this location:
http://www.free-codecs.com/download/Lame_Encoder.htm
1)Once you unzip and extract the files you will find a "lame.exe" archive, double-click on it to run it(nothing to expect, just an ms-dos window for one milisecond or so).
2)Next, cut all these files including the html ones and paste them in the folder you installed Audacity(default location: C:Program FilesAudacity).
After that, open Audacity and export an mp3 file. When the program asks you to locate "lame_enc.dll" file, browse and go to the installation file where you paste it before with all the other files.
I have the 1.2.6 and it worked.