> wild guess: what if you simply make the ":" optional like this:
I believe, the preceding text should be made optional as well (i.e. + should be *, like (string-match "\\([a-zA-Z0-9]*\\):?\\(.*\\)" s))
But anyway, it doesn't seem to work, because for some reason (I just noticed this) - the org-translate-link function doesn't seem to be called at all, when C-c C-o is executed. It is called only in org-element-link-parser.
Also, org-translate-link tries to return the link in the "<type>:<link>" format (exactly the way it expects the input parameter to be). So, simply modifying the regexp shouldn't work because of this as well.
So, I suppose, something like what Nicolas suggests should be done about it (i.e. providing the type and the link in the "new format").
Also, org-translate-link should probably be called somewhere in org-open-at-point again.