That is a very strange problem indeed. I have no other ideas on what could be causing that problem. Unless someone else has any solutions.
Your example shows a particular efnet server, but have you tried connecting to other efnet servers as well as other servers on other networks? From the efnet webpage:
Why can't my hostname be looked up?
This problem likely had to do with either your DNS server, or the one by
the IRC server you are trying to connect to. Unless you happen to run one
of these machines, there really isn't much you can do. However, the
servers with the open I:line should still let you on.
If you haven't already, try looking it up on google:
http://www.google.ca/search?hl=en&q="Couldn%27t+look+up+your+hostname"+efnet-genius_at_work
