I have just had this same issue..
i have deleted and tried to reconnect and it gives me the same error
Invalid Request or Access Unauthorized
I have only just (this morning) converted to a paying shopify store so this is extremely frustrating.. .
I am in the UK, this has been working fine throughout the 3 month trial period and suddenly has stopped.
Any ideas? I really need to get this sorted.
thanks