iPod Headset jack issues - is all hope lost?

I have a first generation iPod Touch and the headset jack has recently gone screwy. The right channel always works, but I have to fiddle with the headphone connection a lot to get the left channel to work, and then it will go out again as soon as the headphones move.

I got this iPod the day they went on sale, so it's out of warranty by now. Does anyone have experience getting problems like this fixed? Is my best bet to take it to a Genius Bar? Or a site like iResq? What kind of bill can I expect? Is there anything I can do about it myself?

Thanks for any advice

I should have mentioned that in my original post. Yes, I've tried a few other sets of headphones.

Does anyone have experience with iPodJuice? Their price is better than I expected.