Well good news, the sitemap suddenly started working without me changing anything!
I suspect that it is #1 that I mentioned above where Google had to update it's cached copy of robots.txt on all subdomains. GWT now accepts the same sitemap with many thousands of subdomains without errors. And I didn't have to add subdomain sites to GWT.
It's a shame this wasn't documented anywhere, since I was about to rewrite the whole thing with separate sitemaps for each subdomain.
So I can now say my above statement was incorrect. GWT *does* support sitemaps with more than 1000 subdomains - it just may show errors for about 3 days while it is updating cached copies of robots.txt (if you recently changed those).