I seem to be running across this error message more and more over the past few weeks. Searches on the internet and Office 365 User Community gave me some suggestions, but not the resolution. I did notice that if I gave it some time, then the issue would appear to resolve itself.
The problem should take care of itself, if you give it more time. The issue stems from replication lag in the Microsoft backend servers. Even though you provision the user account, all the services may not be setup in a timely fashion. I noticed that when I logged into the portal site, that the Exchange services were still being setup. Once the Exchange services were finished being setup, I was able to then verify the Office subscription.
Microsoft has also put out this KB that details other issues with trying to verify the Office subscription.
Thanks for visiting and reading my posts. I am always looking for more ideas. Please comment or email me with what you would like to see.
Office 365 MVP