Spamming my own thread here a little, but I resolved the issue. CircleCI was working perfectly fine (How I could I ever doubted you 
)
Turns out that the URLs for Sauce labs have changed slightly so I was opening a tunnel to one datacenter but attempting to access a legacy one. Once I updated them both to use the correct data center, it all fell into place.