Judy’s comment struck home to me. Something in the whole interaction was deeply off-kilter, but I couldn’t figure it out. Then, while I was at Iceland again, I had a moment of clarity.
The problem, I think, lay in the fact that, yes, people were saying “Sorry” to me (as one would expect in the US) — but they had a funny tone in their voices because they would ordinarily have expected me to say “Sorry” first, where I was saying “Excuse me.” So I said something that (as Mark suggested) sounded stroppy to my interlocutors, and they answered “Sorry” — and I was hearing “Sorry” as part of the conversation — and I couldn’t figure out what was awry with the interaction because I was hearing what I expected. OK, lesson learned, I won’t say “Excuse me” but “Sorry.” I almost look forward to standing in a crowded aisle.