Thing is, their visiting prostitutes leaves the agents open to blackmail, and thus a potential security risk. The degree of the risk depends on whether they are married, a deacon or the equivalent in their church, and so forth. Even if prostitution were 100% legal in both the United States and Colombia, those risks would remain, tho they would be lower. It's not just the physical security of the President that would potentially be at risk. Might not a hedge fund be interested in advance word of what will be announced at the next G-8 summit?
By the same logic though, what if a closeted Secret Service agent was caught visiting a gay bar?
And actually, prostitution is legal in the United States, though I'm sure a Secret Service agent caught going to a brothel while Obama was visiting Nevada wouldn't be treated much better.