sh404SEF was creating URLs in the backend, BUT on the frontend they were only the site domain name or base URL.
The reason turned out to be that the chornoforms plugin was causing some conflict. Upon upgrading Chronoforms this solved the problem.
Case 2: same thing - this time I had to uninstall the whole of sh404SEF + remove all the db tables and re-install. Clear the cache. This time it worked.