I had that happen to me as well. My redirect URL was definitely in at Square Developer Portal. I tried using both live and sandbox access tokes to see if there was a difference but was getting "Client requires a Redirect URL to use OAuth" too.

In the end, what worked for me (if I remember correctly as it was late last night) was to use the live access token.
1. From Zen Cart admin, Modules-Payment-Square, click on 'Log In To Your Square Account' and log on
2. From Square Dashboard, on the left column, select 'Apps'
3. My Apps - Manage App
4. On left column select OAuth. Check that Redirect URL https://www.your_website/square_handler.php is there
5. Show Application Secret and copy and paste this into Zen Cart and update

Fingers and toes crossed!