One nice entry from the Makerbot Math Manipulative Challenge on Thingiverse was GeorgeHart's Five Screw Puzzles. Here is the tetrahedron puzzle from that entry.
Thingiverse link: http://www.thingiverse.com/make:56078
Settings: MakerWare .3mm/low worked well, with no raft or supports (prints in two identical pieces).
Technical notes: PLA can be sharp so don't push too hard while trying to solve the puzzle or you could get sliced up by a pointy or broken piece! If you're forcing it then you aren't close to the solution anyway; the pieces fit together pretty well without too much forcing.
Stuff to change later: Although this is beautiful in the translucent PLA, I think the puzzle would feel better in your hands and twisting together if printed in ABS. Will try this on the Afinia next.