Pychess wouldn't work for me and after trying other software I settled for Eboard. I can play a basic game with it but the interface is intimidating and there appears to be no documentation. Is there a tutorial somewhere or should I try some different software?
glchess (Click To Install)
I played with PyChess (It's in the Software Center) for a while. Among other things, it can give hints for what the best move would be for your current situation. You can also choose the difficulty, so you can start at a low level, and after you've beaten your computer a couple of times move up to a stronger opponent.
You can try using gnome-chess
I would suggest Chessmaster even though it isn't free and only has a bronze raiting on WineHQ, because of the tutorials/lessons by Josh Waitzkin that are really awesome, especially for beginners.
I'm cheating here... But I would recommend Sparkchess or sparkchess.com. The free version is web-based, and doesn't have too many features, but it's a nice interface, and the easiest AI is pretty easy (heck, even I can beat it pretty easily).