I can't help with your unable to restore, but after much hairpulling, I was at least able to extract the data on my desktop and recover some data.
It's a 512 byte header in front of a "tar.gz"
hexdump -C userdata_xxxxxxxx_yyyyyy.backup | less
showed the magical zip header "1f8b0800...