I just went with Gaim .. Loaded the Plugins and whammo.. got MSN.. no problem...
I was having trouble with the exact package name... I'm sure I wasn't looking correctly as you said..
I was able to get VNC server and all running but Everybuddy was even worse..lol
either this one or Trillan on my windows box is always on..