I am having the same problem with Emphathy. I couldn’t get Pidgin (version 2.7.9) to work on Ubuntu. May I ask what version of pidgin, openfire and OS you are running on?
Pidgin 2.7.3, Ubuntu 10.10 - can login with existing accounts, can create new accounts, so I suspect something on the network configuration side - what you get when you telnet to port 5222 from the box with Pidgin?