Used to have a ton of YouTube problems with my GSIII, GSIV, and Nexus 10. From day one, i always thought it was a phone software issue.
Finally got rid of the cheap motorola modem/router combo from TWC and replaced with the newest netgear AC router. No more issues now.....YouTube Vids now load nearly as fast as LTE on phone and Nexus doesn't struggle like before either. Might want to try a friends house before new purchase, but that's my suggestion.
Sent from my GS4 Google Edition using Tapatalk.