Starcraft 2: How do I enable AI difficulties harder than 'easy'?
Your hypothesis is exactly right. Quoting from the Starter Edition page, emphasis added:
What are the Starter Edition restrictions?
Starter Edition players cannot:
- Use versus and co-op matchmaking
- Publish custom maps to Battle.net
- Play offline
- Chat in public chat channels
- Join or create clans
For single player and custom games, Starter Edition players can only play as Terran. Added AI for custom games is limited to Very Easy and Easy difficulty.