So we fixed this by a small mention from someone else here in the forum on another post. The fix is to make sure you are NOT lower casing urls in web.config. We had this rule:

 <rule name="Convert to lower case" stopProcessing="true">
    <match url=".*[A-Z].*" ignoreCase="false" />
    <action type="Redirect" url="{ToLower:{R:0}}" redirectType="Permanent" />
</rule>

With this rule removed the add module functionality works. Apparently some of the modules are case sensitive and have uppercase titles.

Thanks Sebastian,

We figured it out. Some modules use upper case in their url structure and we had the following rule in our web.config:

<rule name="Convert to lower case" stopProcessing="true">
    <match url=".*[A-Z].*" ignoreCase="false" />
    <action type="Redirect" url="{ToLower:{R:0}}" redirectType="Permanent" />
</rule>

With this removed, the add modules functionality works fine. Don't know if I would consider it a bug or not, but worth noting.