In v7.5.8 the previous developer had changed the way that SEO URLs where built, but allowed the ":" character to be parsed (among other special characters). There was a discussion about possible issues resulting in allowing additional characters in the URL (including what we believe is this problem your users are experiencing, see the discussion "Six show stopping problems with UBB.t 7.5.8's new Spider Friendly URLs
"), and a fix was quickly posted, but not used in the final build.
To test this as a potential fix for your reported issue, you should have your users remove the ":" character (or any other non alphanumeric characters, with the exception of "/+-") when they're unable to connect, to see if it will then allow them to connect.
When we created v7.5.9 we decided not to want to have users lose their search engine ranking with another URL scheme change, and were holding that back until the release of v7.6.0 which should be released within the coming months.
You can find the v7.6.0 version of the link coding at UBBDev: [7.5.8] Better URL Sanitization for SEO
If you choose to change the way your URLs are built (either by installing the "Better URL Sanitization" modification or upgrading to v7.6.0 when it is released) I have a UBB.Sitemaps
tool available which will aid in the process of Search Engine Discovery for the new URLs to Search Engines that support Site Maps.