I think the... problem, for lack of a better word, with just saying "Excuse me," is that it can also be used to get someones attention. So with PPs who have said excuse me to a child only to have them stare blankly, it could be because they think you're using it that way (e.g. "Excuse me, can you tell me where the restrooms are?")
So I think, "Excuse me, I need to get past please," might yield the best results.