Very happy to hear that got it working for you. I've done some more investigation as to how Joomla is doing it. They do use the method that I had you change. One thing you may want to check is if your Joomla Global Configuration setting for SEF URLs is enabled. Even with sh404SEF, or any other 3rd party SEF extensions, you should enable the core-Joomla SEF system. The others will override it, but extensions (like ours) will use that setting to know if you're using SEF URLs.
Please let me know if your Joomla SEF setting is enabled. If you want to test something, you can try enabling it and undoing the change I mentioned above. That should also work. I recommend this as we're not certain if we'll be implementing this change in the upcoming 4.1.1 release, so it'd be good to know if we can get around it through the Joomla Global Config setting.
Thanks, and again, glad to hear you're at least going now!
Alex