Can't invite users - ‘Sorry, we couldn’t invite that person’

I just tried and invite works fine when entering an unknown email address. Are you sure you entered a valid email address? Did the invite dialog change when you entered the email address?