Whitney Hess has one of the more awesome guides to becoming a UX Designer on her blog: "So You Wanna Be a User Experience Designer". Very, very good resource for junior folks just getting started. Another great resource is "Getting Started in User Experience Design" from Evantage Consulting.
As an existing designer who is transitioning into UX, I would say that you actually have a strong advantage, as you should be able to explain why projects that you've worked on in the past represent great experiences, and be able to talk through the process that you went through to get to the end product. While some of the methods that UX'ers use are a bit specific (e.g. usability testing, card sorts, etc.), almost everything can be learned as you go if you already have knowledge and passion for creating amazing experiences.
That being said, if the company was looking for someone who was "ready to go on day one" for leading a project, then you might not have been the right fit... but I promise, there are tons of companies out there who are willing to work with people who have the knowledge and passion (but who may lack in direct experience).
Direct experience, to me, would mean working in UX-specific deliverables. Flow diagrams, personas & scenarios, wireframes, specifications, heuristic analyses, usability tests, and so forth (More info on UX deliverables). When we hire, we look for a UX portfolio that includes samples of things like that -- helps us evaluate a candidate's thought process. But I was hired for my role without a portfolio, because I can speak to how my previous (non-UX) projects were designed to improve our users' experiences.