I have the same problem. Direct connection to the Internet but LW says Firewalled.

Details requested:
1. OS version? (eg: Windows 98) Ubuntu 6.10
2. What firewalls you have? None
3. How much ram? 2GB
4. Hard Disk space available? 100GB
5. Connection type? (eg: dialup, broadband, cable, etc.) 8Mb broadband
6. Modem & router brand name & model numbers? Cisco 800 series
7. Where are you trying to connect from (house, appartment complex, school, student accomodation, work, etc.)? Home
8. What version of LimeWire (LW) & Java do you have? (Go to LW's menu Help>About LW...) Will show both LW & Java version. Sun JDK 1.5 LW 4.14
9. Who is your ISP (Internet Service Provider)? BT
10. Do this simple test for us. Using your browser go here: http://www3.limewire.com:6346/ The page should say 'Your test worked!'. What happens when you go there? Test worked
11. Are you sharing the connection with other computers or p2p sharing programs? If yes, please give details of set up. No
12. Is this a your 1st try at LW or is this a new problem with an experienced user. Experienced user trying to work with open source but frustrated with inability to get rid of "FW" and so complication with UltraPeer mode. (I know there are other factors for UP)
13. Do you see a brick wall in front of the blue world icon at the bottom of LW's interface? Sure DO
14. For those using a modem/router, how is your modem/router set up...are you port forwarding or is UPnP enabled? Wide open for this IP. Routing only nothing else.
15. What security programs are you using (antivirus etc)? Some people might not be aware that their security suite includes a firewall
Nothing. Vanilla Ubuntu
16. What country are you living in? Sometimes there are ISPs with the same name in more than one country (eg Clearwire in the USA & also in Ireland). UK