Having the same issue. Totally new to Workflows and didn't understand how things just suddenly started breaking. (just released to Production for the very first time today, real bad timing! 
)
Thanks to @bobthebear for your post (Unable to test query block: no access) - that's how I finally found I wasn't alone in this.
In case it's at all helpful in troubleshooting/resolving the issue: I also noticed that one of my workflows somehow fell off of the "Usage" list for the specific REST API Resource that appears to be broken when trying to execute individual blocks. There are TWO Workflows using that Resource, so it doesn't make sense why only ONE of them shows in the "Usage" list.