I figure it's like Fermat's Last Theorem, an easy problem to state but a hard problem to solve.  

I've actually done a bit of extensive collaborative work on LOOKING at the problem and it's intrinsic nature.  I've been doing that since the Joint Meetings actually.  I was staying at a Hostel with other people from my school and there was a guy from the University of New Hampshire in our room (6 people to a room, 4 from our school, 2 "strangers" - other math people, it was cool) and we e-mailed a bit and he referred me to one of his students.  

So we've been collaborating ever since.  

I'd recommend to take a bit more math, but there are some really reachable papers about how graph theory relates to it and stuff.  Graph theory and looking at Modulus will help give you a step up on it.  It will also save you a lot of time from looking at dead ends...

Hope all goes well in your math endeavors though, don't give up.  Realize that math is so vast you may never know one thousandth about any particular area of math and that you need to just keep on chugging on and learning math.  Not many people I know are happy with their math skills, but it's not something you should hate yourself about.  

E-mail if you want more info and links to a few really great articles.