This is interesting since you can download playlists. It implies your WiFi connection is good, although the errors you gave indicate there is a connection issue.
Since your Connect is right out of the box, it should have gotten a firmware update downloaded while you were connected via WiFi. Did you see any messages stating that? If you did, make sure you reboot completely by holding the power button about 8-10 seconds and then powering up again. The current firmware version is ZAP 18.104.22.168236r.
Also, Yahoo made some station changes recently and your directory might need updating. The typical messages on any stations that were removed should just say either ‘can’t find station’ or ‘can’t find host’. You can try forcing a directory update by going to the Internet Radio menu > select the ‘Options’ button > choose the ‘Refresh All’ option.