I did a cross-cultural developmental psychology experiment on the way children think about magic. In brief, children in the USA showed an inverse correlation between their ability to understand something and their attribution of magic (i.e. if they didn't know how something worked, it was magic, and vice versa). In Mexico, I found that the correlation was not so mutually exclusive, children were willing to attribute things to magic, even if they knew how it worked.
Understanding magic not as something distinct from science, but as something that is the realm of things which you can explore to understand better is, in my opinion, a better way to frame the debate. Telling someone to stop believing in magic because no such thing exists is unlikely to change their belief system. Encouraging them to explore magic, and seek to understand it and find the magic in everything around them, has a greater chance of spurring them into a more inquisitive frame of mind.
The theory of Wonder I developed for my masters thesis posits that wonder is an emotional trigger that positively rewards us for finding things that we can't explain. The evolutionary basis for this is that the more things you find that break your world view, the more likely you will learn something to new that will positively effect your ability to survive. This could explain people's fascination with magic: we have an innate drive to find the things that baffle us, an internal reward system for experiencing wonder.
I could go on about this for days, so I'll just stop now.