I had exactly the same problem.
Had the redirection plugin installed before and deinstalled it, thinking not needing it anymore. And after a reinstallaion I was not able to add any redirection and there were also no modules available under the module tab on the plugin options page.
After deleting the 3 by coffeehero mentioned tables everything worked fine! This issue should be mentioned on the plugin page within the faq section. It took me several hours on 3 days to find this solution.
Thanks a lot, coffeehero!
