A cloud provider who supports Ubuntu and not Debian almost certainly doesn't know what he's doing; I'd consider it a warning sign, although not an outright disqualifier.
We are in fact leaving them by the end of 2014, er the end of 2015, er some time in 2016. (It turns out disentangling years of encrusted dependencies is complicated.)
But in practice, Ubuntu is a perfectly good version of Debian for our purposes, so we'll probably stick with it. The devs also like it on their desktops so feel happier targeting the same thing on the server.