I originally threw out "horns of a dilemma" but the preposition attached to it was not anything crucial to me. Although, it does make sense to me to say "between" in that one has not yet made one of two undesirable choices. Each horn represents the undesirable result of one of the choices. But if the world wants to say "on the horns" -- I suppose it's as if the predicament itself were as painful as being skewered by two horns -- then fine by me. I'd much rather spend my energy trying to get people to use their turn signals.