It's a DNS problem. Basicaly your Pandora is connected to the internet but it doesn't know which DNS server to use.
A DNS server is basically a invesed dictionnary that matches URL to IP address.
Usually when you connect to your router it is configured automatically however that does not seem to be the case. There can be compatibility issue between some system and router.
A simple way to fix this is to specify the DNS server manally. Pandora uses "Network Manger" which takes care of all your internet connection needs. You should be able to specify a DNS certain to be used with a specific connection.
What you need to do:
1. Find out your DNS server IP (check your Internet Service provider webpage). Alternatively you can use a 3rd party DNS server such as OpenDNS (http://www.opendns.com - DNS Server: 208.67.222.222 and 208.67.222.220.
I would recommend you to stick to your ISP dns server unless you have a problem with them.
2. Configure Network Manager. You need to right-click on the Network manager icon, then select "Edit Connection". From there you should be able to configure the DNS server for your connection.
Here is a tutorial on how to set it up. (It's for OpenDNS and Ubuntu but it's the same - just input the DNS server IP you want to use)
http://www.ubuntu-inside.me/2009/05/howto-use-opendns-on-ubuntu.html
Hope this help.
EDIT: As expected some other ppl beath me to it.