Having the same problem on Pithos 0.3.17, but getting status code 7, 3:

Started doing it on Saturday about 1/4 of the time, but on Monday morning it does it 100% of the time and plays nothing.

I have no proxy on my network.

pithos --verbose
INFO - pithos:<module>:828 - Pithos 0.3.17
/usr/bin/pithos:805: GtkWarning: Ignoring the separator setting
  builder.add_from_file(ui_filename)
INFO - plugin:enable:35 - Enabling module notification_icon
INFO - plugin:enable:35 - Enabling module mediakeys
INFO - mediakeys:bind_dbus:32 - Bound media keys with DBUS
INFO - pandora:connect:172 - Time offset is -3.05723309517
INFO - pithos:pandora_ready:328 - Pandora connected
INFO - pithos:process_stations:348 - Restoring saved station: id = 23339642589642471
INFO - pithos:station_changed:541 - Selecting station 23339642589642471; total = 26
INFO - pandora:get_playlist:247 - pandora: Get Playlist
INFO - pithos:start_song:386 - Starting song: index = 0
INFO - pithos:art_callback:468 - Downloaded album art for 0
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin0/GstSoupHTTPSrc:source:
libsoup status code 7, 3
INFO - pithos:start_song:386 - Starting song: index = 1
INFO - pithos:art_callback:468 - Downloaded album art for 1
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin1/GstSoupHTTPSrc:source:
libsoup status code 7, 3
INFO - pithos:start_song:386 - Starting song: index = 2
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin2/GstSoupHTTPSrc:source:
libsoup status code 7, 3
INFO - pandora:get_playlist:247 - pandora: Get Playlist
INFO - pithos:start_song:386 - Starting song: index = 3
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin3/GstSoupHTTPSrc:source:
libsoup status code 7, 3
ERROR - pithos:on_gst_error:554 - Gstreamer error: Could not read from resource., gstsouphttpsrc.c(1097): gst_soup_http_src_parse_status (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin3/GstSoupHTTPSrc:source:
Connection terminated unexpectedly (7), URL: http://mediaserver-sv5-rt-1.pandora.com/access/?version=4&lid=29196007&token=XT7O4HzE1qmBi0vQBSHTruVNRBkhFPHUZ30biOoxdqNqVGaBIxuW4388BCqpwhjFFYt2%2FO5otyPIk0hvOadPc5eF%2BkgHGeuxQZqudFme9%2BZ%2B6kqGZrOjoAl4dmOwhUt3k83tCB%2Bs0NsWymHVAjzPEMEQHHFq5hEeeLnOnIx3Vx2nObkgkE%2B%2B%2BCjY4xBykhoFD8y2eSGrHrrVyzqqhaLdYYC0F865hVLsMxmMivgjnRD%2FmGxPmR%2BNcyZXSYYvczycfanF%2BMTiaFq8CYCBv%2FAVctcKdTT6Uajd%2FWPKZyNiqmNMOVHNlQsp2B3z9ACTfZOEllGihi7udNLS5MlAOynlYJR%2FognFMYnGYOqbstJwlsxns3s7JZK7sXORu%2Bd4mfg%2FsdtFynBR8yHcotHm2uNeg8FGaK7vkgGvGOprA1%2BjkHNODEzMjGSggTbZwXFnWCX4g70eoAKEbz7CQsNGmmRDUo6mYgKXu5O0%2F2Rfrq85JiJ9oTuW1cMporE8%2FYLh2Xyneias5VBa9Ss8FP8SWLpqIIqZ1qoA9DpG%2FAlYw50tBwhtKtm9%2FQn46w%3D%3D, 9
ERROR - pithos:on_gst_error:554 - Gstreamer error: GStreamer encountered a general stream error., gstbasesrc.c(2625): gst_base_src_loop (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin3/GstSoupHTTPSrc:source:
streaming task paused, reason error (-5), 1
ERROR - pithos:on_gst_error:554 - Gstreamer error: Could not determine type of stream., gsttypefindelement.c(570): gst_type_find_element_handle_event (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin3/GstTypeFindElement:typefindelement3:
Can't typefind empty stream, 4
INFO - pithos:art_callback:468 - Downloaded album art for 2
INFO - pithos:art_callback:468 - Downloaded album art for 3
INFO - pithos:start_song:386 - Starting song: index = 4
INFO - pithos:art_callback:468 - Downloaded album art for 4
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin4/GstSoupHTTPSrc:source:
libsoup status code 7, 3
INFO - pithos:start_song:386 - Starting song: index = 5
INFO - pithos:art_callback:468 - Downloaded album art for 5
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin5/GstSoupHTTPSrc:source:
libsoup status code 7, 3
INFO - pithos:start_song:386 - Starting song: index = 6
ERROR - pithos:on_gst_error:554 - Gstreamer error: Resource not found., gstsouphttpsrc.c(924): gst_soup_http_src_finished_cb (): /GstPlayBin2:player/GstURIDecodeBin:uridecodebin6/GstSoupHTTPSrc:source:
libsoup status code 7, 3
WARNING - pithos:get_playlist:460 - Too many gstreamer errors. Not retrying
INFO - pithos:art_callback:468 - Downloaded album art for 6
INFO - pithos:art_callback:468 - Downloaded album art for 7