Yes, you can do it.
My friend and I started CrossFit together in mid March (3x per week and he would do 1 private session that mostly worked on his flexibility and some basic movements ie. squats). As of this saturday he has lost 59 lbs.
2 months ago we started eating Primal (Primal Blueprint (
www.marksdailyapple)) and haven't looked back. He has about 60 more to go, but there is no question in my mind that he will get below the 200 lb mark within a year. NONE.
I had possibly 10lbs (started at about 148lbs) to shed and am leaning out and getting stronger. EVERY DAY after our first few weeks of crossfit we were both dead tired so it isn't just the chubbies that get sore!
Now that we are getting stronger and eating healthier our recovery is that much better, but there are still days when a body part is sore or feels tired. That is part of the fun of the workout!
Accept the soreness, embrace the soreness because it is good pain and you will be better for it.
There is a Crossfit t-shirt that says: "that isn't sweat, it is my body crying". It is painful and hard for everyone, but nothing worth doing comes easy.