Truncated Tetrahedron
This polyhedron can be made from 5 different colors. Each of the truncated faces (4 hexagons) will be a different color. The truncations (4 triangle faces) will be a fifth color.
To see the full sized template click on this image: 
You will need four of the hexagon faces in four different colors and four triangle faces that are all the same color.
You can assemble the polyhedron by attaching 3 hexagonal faces to one of the triangle faces. The 6 edges of each hexagonal face will be glued alternately to a triangle and then another hexagonal face. All of the triangular faces will be surrounded by hexagons.
