In ceilings tend to be more diffuse than in-wall for surround duty when placed correctly (behind, not directly above). I was skeptical it would work for my friend, but he had a large area and no rear wall so he went in ceiling and it worked surprisingly well.
I presume the basement is finished or the wires would be running across numerous beams, which would make it more time consuming, so I sort of understand their assessment. If you are talking to AUDIO installers, then they may be right about your situation, however I've found that general contractors usually don't know squat about audio and install what they THINK will work, not what will actually be best. If they're running the wires up there, there's no reason you can't still use the HTMs with mounts.
What did Salk recommend for surrounds? Have you heard the HTMs? I don't really think the HTMs and the Songs are going to be well matched timbre wise, though it is less critical for surrounds. In this case though, I think they're going to be pretty different.