Found the issue and the solution!
Basically, Apple TV logs in the sandbox user to be the default user on Apple TV automatically. That means, that a non-sandbox user gets logged and tries to make a sandbox purchase, which causes the error.
To solve this:
Settings
Users and Accounts
Sign out the Sandbox Account
Login with a normal sandbox user
Do the purchase.
Hope this helps!
Topic:
App & System Services
SubTopic:
StoreKit
Tags: