First things first, check your headphones. Just as a precautionary measure (And you'll probly respond with somethin like "what do you think I am, stupid?" - but we all forget small things)

So long as it's not your headphones, I would very highly doubt that it has to be resoldered to the board, and I would think that it sooner needs to be cleaned/replaced. To have intermittant connections that are fixed by twisting the plug in the jack....I very highly doubt it would have to do at all with the soldering job.

Whether it's easy or hard or anything, chances are it won't be terribly easy, but won't be impossible. There's also a pretty good chance you will damage your player in one way or another by opening/attempting to open it...that's just from experience though.