If you have a few quid to spare you might think about using the Lego Brickalizer:

http://shop.lego.com/shopmosaic/default_s.asp?

This lets you upload an image to be used to make a mosaic from Lego bricks. The Mosaic ends up as a 44 x 44 bitmap which you assemble as a picture. It costs around 25 quid so it is a tad expensive, but I just had to try it (there goes my pocket money for the month). I'll let you know what it looks like.

If you don't fancy buying the bricks, and you have your own lego bricks, you can use the program to print out the just the instructions for your image. Your browser needs to run Java to support the mosaic applet. Actually, I found that it worked best if you use another program (I used Digital Image Pro) to pre-process the image into the correct size and then just tweak the contrast and brightness using the applet.

I reckon it might be a neat idea for a present for someone special.