Seeing as the going claim is that there are only 36 ways to paint a tetrahedron using four unique colors, I'll endeavor to count them. Below I have 'drawn' a tetrahedron for visualization purposes:

                             ,|,
                           ,7``\'VA,
                         ,7`   |, `'VA,
                       ,7`     `\    `'VA,
                     ,7`        |,      `'VA,
                   ,7`          `\         `'VA,
                 ,7`             |,           `'VA,
               ,7`               `\       ,..ooOOTK`
             ,7`                  |,.ooOOT''`    AV
           ,7`            ,..ooOOT`\`           /7
         ,7`      ,..ooOOT''`      |,          AV
        ,T,..ooOOT''`              `\         /7
       `'TTs.,                      |,       AV
            `'TTs.,                 `\      /7
                 `'TTs.,             |,    AV
                      `'TTs.,        `\   /7
                           `'TTs.,    |, AV
                                `'TTs.,\/7
                                     `'T`
There are two ways to paint a T (tetrahedron) with a unique color for each side; one is the mirror of the other.

There are 24 ways to paint a T with three unique colors. Four possibilities for the two that are the same, three for the first unique, and two for the second unique = 4*3*2 or 24. It is not possible to create duplicates, since duplicates are taken care of by successively reducing the number of possible colors for the next consecutive side.

There are 12 ways to paint a T where three sides are the same: 4 possibilities for the three same sides, three remaining possibilities for the remaining side for a total of 4*3=12. Again, duplicates do not exist.

There are four ways to paint a T where all the sides are the same (if it is imagined that four is the total amount of colors available).

Now, to total the results: 2+24+12+4=42. Hmm. I don't count 36. Theory and reality not quite in sync, or are my figures wrong? Just a side note, if mirror images aren't allowed, this doesn't quite cut the numbers in half, but close. They would become 1+12+12+4=29.

Update: 15:51 Tue Aug 22 2000

In reply to mblase, umm, I still have to disagree, and even add some more to my list. Remember, a mirror image is one such that no rotation can achieve it while still within the same dimension (i.e. a left hand cannot be rotated into a right hand while still in the third dimension). So my original count for three unique colors is still accurate. For two unique colors, I concede the point. So that's another six onto the original, or 48, or another six onto the secondary, or 35. I have done the work on paper and I believe it stands as I have stated it.

Update again.

Now I see the light. It took quite a bit of imagination (something I have trouble with . . .). The count is 36. So much for counting accuracy . . . The operative case here is a tetrahedron viewed on an edge. Two unique colors are on the faces visible, a third unique color is on the faces that aren't. The two visible faces can be rotated either way 180 degrees to produce a mirror image (so much for my mirror "logic" above), so there are only 12 instead of 24, and the count is 36 (or 35 if mirrors aren't allowed . . .;).
Final note: I don't intend to "fix" the mistakes above . . rather I wish this to represent a process of thought that may (or equally well may not) be useful to someone wishing to understand. My mistakes above are legitimate; I really did think I was right for quite some time (an hour at least . . .).