Solved my own issue. By disabling the "Redirect caching" option... It really was as simple as that.
I still like this plugin, but after looking at the code structure and seeing all the minor errors it produces when you turn on debug mode, I've got to be honest and say there is room for improvement there. I'm swamped with work now, but (if I'm keeping this plugin around) I'll be sure to have a look at these issues eventually.
From what I can tell it still beats the heavier caching plugins on low resource setups, and to be fair I've not checked to see how many errors these heavier plugins produce.
The option fixed the 'redirect loop' issue. But then it did not cache the paged archives and categories. To fix this I had to comment out line 290 in
wp-content/plugins/hyper-cache/plugin.php. So far everything is working great.