1) Sounds like you did this but make sure web browser can load pandora web site
2) Restart Nook and retry
3) Remove Pandora app and re-add and try.

None of this works and the Pandora app came on my NookColor when I looked at the already given apps. Half the time my internet does not want to work on it but it says its still perfectly connected to my wireless internet. Could it be that I need to Update it or Root it or even just my internet connection is too weak for the app.? I just got it for Christmas 2011 and I am not quite sure what to do about this all.

If the internet isn't working correctly all the time I don't think the problem is your pandora app. It could be your nook interacts poorly with the router you have, you might try a different router if you have one or go to the store and try their wifi if that's an option. I doubt it's the app, but your networking. What router do you have? You have tried restarting it and remove/add the network connection?

I'd try in store - if works it's your router. If not get an exchange. It's a great device.