Well not sure what cPanel version you are using, but my hosting company(the one I own), does use the cPanel backup, they are weekly, and I have used it for a FULL server restore, which did work, and yes ALL the databases where there also. We also include ALL websites, not just this 10GB stuff, that most crappy hosts do. "Why are you selling unlimited hosting, if you can't provide it?" That's my question....
This is a HARD fact to learn the hard way. I'm sorry Josh, that sucks, but I would be finding a new host if I was you!