An undergraduate friend of mine told about this website, and I became a little obsessed with reading the posts that have been made here. I felt like I had to respond to yours.
Though it's not the case 100% of the time, most entering PhD students hold Masters degrees. Stanford, Yale, and Princeton all receive over 100 applications yearly, and accept a very small fraction of those students--and generally, those students hold Master's degrees. I know it's favorable to forego the MA completely to enter a fully-funded PhD program from the get-go, but the truth is that students who have had more research experience and can show evidence that they're capable of writing longer work are much more desirable candidates to PhD adcoms. You seem to be on the right track with what you've done so far as an undergrad, but it also seems that the programs you've applied to are all on a PhD-only track--without a terminable masters (excluding Columbia, I believe).
As a 5th year PhD student at an Ivy (in Art History), and as someone who has sat on the admissions committee twice, I would recommend (if you are unlucky this time around, which I really hope you're not!) working REALLY hard on your writing sample. It's probably the most important component of the entire application--more so than recommendation letters and grades. Internships demonstrate your passion for the field, but they aren't really evidence of scholarly potential. Your GRE score is fine -- the Q score is hardly looked at. And if you haven't done so already, I'd suggest presenting your research at a couple of conferences. Beef up your language skills, as 3 years of one foreign language is a pretty common asset among perspective applicants.
Good luck! I do hope you hear some good news soon!