There are exactly two ways to paint a tetrahedron with exactly four colors. Because of how a tetrahedron rotates, one of these paintings will be an exact mirror of the other.
With three unique colors, you must have two sides the same color. (And because it's a tetrahedron, these two sides will always be adjacent.) You have four unique colors for these two sides, three for the third side, and two for the fourth. But, half of these tetrahedra will be rotations of the other half (the third side red and the fourth blue is identical to the third side blue and the fourth red, if you view it on an edge and spin it 180 degrees), so you need to divide by two: 4*3*2/2 = 12.
Where three sides are the same, you can have four unique colors for those three sides, plus three for the fourth: 4*3 = 12.
You can also have two sides be one color (out of four), and two be a different color (out of three). There are 4*3/2 (rotations again) = 6 possibilities here.
Finally, there are four colors you can use to paint all sides the same. The final total is 2+12+12+6+4 = 36 possible colorings.