I spent almost a day on making this work, first of all because I didn't have a freetype enabled gd, even though I did have freetype installed, so I had to rebuild everything.
Then, I was using transparent backround and as any normal person out there I did not bother to read the hints of each config option so naturally I did not set the background color, making things look bad so I upgraded my freetype to latest and had to rebuild yet again (I have to learn how to upgrade without rebuilding everything).
Anyway, eventually I got around RTFM-ing after exhausting every other option, just like any other normal person :D and that solved it.
My menu troubles came to an end. The exact width combined with centering helps on creating a nice horizontal menu. It rocks :)