Sound change seems to be licensed not only by gradient changes of place of articulation but also by percieved similarity between an "easier" and a "less easy" sound. Of course, which sounds are easier is not always quite rational. An example of this would be German x/ç --> f, which has radically different place of articulation, but sounds similar. Something like that might have happened.
Another explanation for seemingly random sound changes is of course that both sounds are innovations and that originally there was one that was more similar to both of them.
The fact that sound changes don't have a provable rationale, as fdb mentions, doesn't mean that there aren't any reasons or regularities at all for sound change, and there are indeed some sound changes which you encounter regularly and some that are virtually unheard of, unless you assume some intermediate steps. For example, PIE /s/ --> Albanian /gj/ or PIE /sw/ --> Albanian /d/ are so strange that there are, as far as I'm aware, no scholars maintaining that this happened in one step.