Minecraft – What happened to the trees

Trees can definitely be grown underground with sufficient light. According to this thread on the Minecraft Forums, you need 7 blocks of space above the sapling. (Perhaps this condition isn't being satisfied.)

Update: According to Notch's blog post about changes coming in 1.6, the torches-on-fast-leaves bug is getting fixed:

• Fixed buttons and levers being placeable on leaves in “fast graphics” mode

This means that monsters can no longer spawn on leaves, either, as they are always considered transparent, even when using Fast graphics.

Monsters can spawn on any solid, non-transparent block which is at light level 7 or lower.

Signs, torches, rails, and the like are ignored when spawning monsters; they'll spawn on the block underneath just fine. This is why one-block-wide railways need to be lit.

Transparency means whether or not light passes through a block rather than whether you can see through it. Half-blocks, doors, stairs, and glass all count as transparent and prevent monster spawning. Leaves, oddly, count as transparent only when Fancy graphics are enabled. An easy way to test a block for transparency is to try placing a torch or sign on it — neither can be placed on transparent blocks. (Meaning that torches can be placed on leaves with Fast graphics, but not with Fancy.)

Torches put out light level 14, so monsters can't spawn within 5 blocks of a torch orthogonally or 3 blocks diagonally. If you put your torches in a diamond pattern, they can be up to 9 blocks apart, but it's best to move them closer than that on uneven terrain. (I use 5 myself.)

If you like, you can actually torch your treetops by changing your graphics to Fast, placing the torches, and switching back. Your torches will stay rooted, even though you wouldn't normally be able to place them that way. Personally, I think it makes them look rather cheerful. :-)