The problem here is not matching a colon, but that you've been taught that vim MUST use a colon to seperate it's regex. This is incorrect.
awk/vi/perl/ruby (and many more) let you specify wahtever delimiter that you want. This character is the one following the command character (in our case an S), eg:
s/hello/there/
s:hello:there:
s@hello@there@
are all the same regex, just with different delimiters. This flexability means that if you often use /, but you then need to match a / in the regex, then you can just switch to some other delimiter, eg:
sMhel/loMthereM
Though "M" might not be the best choice when the regex contains text -- it depends on your style and what you're matching really.
You can even use brackets. For a single regex it is:
s[hello]
or
s(hello)
I think for the search and replace style you can use s[hello][there]
or possibly even s[hello](there)
. But this last sentence about the brackets is a half remembered guess from when I alst used perl.