I was in a very similar position to you when I applied to grad schools. I had a really terrible GPA my freshman and sophomore year because I started out in a difficult field that wasn't right for me, but once I found my focus, switched majors and began getting better grades, I pulled my GPA up to a 3.1 by senior year. And you know what? I got accepted into most of the schools I applied to, including some top tier ones like SIPA and SAIS. So don't feel discouraged by your grades - use them to your advantage! In an admissions essay, explain how switching schools made you figure out what you really wanted. Make sure you dominate the GRE and take your time getting your essays right.
But if you have a notsogreat GPA, I've got to say that work experience becomes incredibly necessary. I had about 3 years between undergrad and g-school, working in my field. I think that's the only reason I got in anywhere.