So after so investigating I saw that others where having a similar issue with large sites.. 15+ GB. Now... my site only tops out at 1GB or so. There shouldn't be a problem right? Well if you consider that the underlying problem could be the actual room left on the physical drive you get closer to the issue here. With some IT outfits servers are deployed with a dinky C drive/partition for the os and a much bigger D drive/partition for 'Data'.
This setup does not work for SharePoint. Yell at your IT colleges if need be. There are some things that can be sloughed off to the d drive, but a lot of stuff happens on the C drive that you don't have control over. One of these is where SharePoint puts the temp file is uses during restoration. You guessed it the C drive. In addition it just makes sence not to have to move everything to the Data area for no reason. (If someone can tell me why people do this... it would be great.)
If that drive is fragmented and is down to it's last 100 MB or so stsadm will not be able to complete building whatever is in the temp file.
The answer here is to make sure that you have enough room for that temp file to be created. A good rule of thumb that I go by is that no partition should have less then 15% free disk space. This was a good rule in previous Windows OS's and I'm sticking to it.