Weird. I hadn't seen this thread, but I started making random trees the same day it kicked off.
I was using an approach like the one Quazi was talking about - branches spawn smaller branches until you have a tree (using randomisation at each step).
Here's the cap:
http://dl.dropbox.com/u/906550/Construct/noise6.cap
And EXE, in case you have an older version (I'm on .84, the latest):
http://dl.dropbox.com/u/906550/Construct/noise6.exe
Press Q to grow the trees by one step. You should probably stop after about 8-12 steps, because the number of branches increases exponentially.
I haven't gotten foliage working yet. I had something that looked reasonably good, but it's ridiculously resource-intensive (and so I ended up having to paste it into a Canvas object after, which really reduces the amount of stuff like wind effects you could do). A lot of the fractal trees I've seen in 3d actually used a very similar method to make the foliage after the branches were done, so I might try that.
(If you like how this approach looks and want to use it, I'll see if I can make up a cleaner .cap so you can see how it works - there's a lot of crappy, leftover, and unrelated eventing in the current one.)