Awk works for me:
grep string files | awk -F":" {'print $1" : "$2'}
Just a bit of explanation, if it would be helpful: The format {FILE}:{MATCH} from a multi-file grep is piped to Awk. Awk is told to use a colon (-F":") as a delimiter for identifying fields and then the following reformatting occurs: Print the first field (FILE), then print " : ", then print the second field (MATCH).