Okay, you did nearly everything correctly

But the tree you used still had a white background. When using the brush, it will not only paint the tree, but the white background as well, and therefor it will appear on top of a white block.
To get rid of the white background, you either go "Colors > Color to Alpha" or "Color to Transparency" and choose white as the color you want to remove (warning, this will also delete the light-green parts of your tree and therefor make the tree itself a bit transparent) OR you make it the better looking way:
-Open up the BRUSH.GBR in Gimp (the file itself!)
-Click on the wand tool in your tool dialog:

-Then click on the outside of your tree which is white.
-Go to "Select > Feather" and set 2 as your value.
-Hit the delete button on your keyboard some times.
-Save it again and put it back into your brush folder.
By doing it this way you remove the white background without changing the tree itself. This is how it should look like in the end:

(Same tree but without the white background)
Link for the finished .GBR file:
https://rapidshare.com/files/460478665/TREE_1.GBR