We use K2 and XMap on all our sites, and we don't have failed sitemaps.
Be sure to enable K2 plugin for XMap.
Be sure to get the correct URL of the sitemap to submit (if you use some SEF component, it may change your sitemap URL, and that may cause a problem). Copy and paste the URL from the sitemap window, and use it directly on GWT.
If your site is huge (I have one with about 20k pages, K2, and it take a while to generate, but it doesn't fail), increase the timeout, compress the sitemap, don't use intro text, menu title, class, #cols, don't beautify, and don't link to author. Keep it as simple and plain XML as you can.
"Use a good host" helps in every scenario. Host-on-a-budget never, ever, works. I like to use the "meal parameter" to hosts. If it cost less than a full (even if cheap), good (not fast-food), seated-in-a-nice-table, diner, then it will suck. Anything less than $30/month isn't worth your attention (and for $30 you get a nice small VPS on US or UK). Or, you know, there is always "Blogger" for free...