What size companies were you applying to? I've heard that smaller corps tend to put emphasis on CS education, while the big ones (big enough to have research divisions, like Google and Microsoft) are happy to consider people from other quantitative fields so long as they can code and know something about algorithms.

I know people with math, statistics and aeronautical engineering backgrounds who've worked at Google and Microsoft. I'm sure physicists would fit in too.