<p>I found a story about someone <a href="http://www.fablabamersfoort.nl/en/node/534">3D-printing equipment for their Lego minifig</a>, using an Ultimaker. (Article is in Dutch, but accompanied by photographs).</p>

<p>I noticed that what they made weren't the actual connecting bricks, but the tools used by the minifig. And that even so, some filing and a dremel were needed afterwards to make them fit properly.</p>

<p>I'm told that to make something connect properly with real Lego, the machine needs to be tuned very precisely.  </p>

<p>So, what resolution is needed to print bricks that will connect with normal Lego bricks?</p>

It's really more about calibration than resolution -- a poorly calibrated printer will have dimension errors that prevent mating with true LEGO bricks or other printed bricks.
Also, "resolution" is an incredibly loaded term for 3d printers, because it can mean a lot of different things. But we don't need to get into that right now. There are really two big things to worry about: layer height and extrusion width.
Layer heights of 0.1mm or 0.2mm should be fine. Coarser layers may run into surface finish issues that make the bricks difficult to put together or take apart. There probably isn't much reason to go finer than 0.1mm for this application. Almost all FFF printers can do 0.1mm layer heights as long as it is reasonably well-tuned.
Any typical household FFF printer with a "normal" nozzle size can print fine enough for the bricks to work. It just needs to be tuned well.
The smallest "must have" feature in a standard lego brick is the 1.6mm thick wall around the sides. The typical minimum printable feature size for an FFF printer is 2x the extrusion width, because the slicer will place a path on the inside edge of the shape and the outside edge of the shape. (Some slicers will allow single-extrusion features, but this is not generally recommended because it makes weak parts.)
So, how wide is the extrusion width? It's adjustable, and different slicers auto-recommend different values, but as a safe rule of thumb it needs to be between 1x and 2x your nozzle size. There are some volume calculation quirks in different slicers that may encourage larger or smaller sizes, so sometimes people recommend [extrusion width = nozzle size + layer height] particularly with Slic3r. This is very system-specific.
Assuming you have the most common stock nozzle with a 0.4mm orifice, and also set the extrusion width to 0.4mm, the slicer should put four strands in the walls of the LEGO brick. That's good.
Where it gets tricky is if you have an extrusion width that does not evenly divide into 1.6mm. Say you are printing with an extrusion width of 0.6mm. There is enough room in the wall of the part to place two full 0.6mm perimeter strands... but then a gap 0.4mm wide will be left in the center. You can't put another 0.6mm strand into that 0.4mm gap. Different slicers handle this different ways. Some will leave an empty space between the walls, and you get a very weak print. Some will mash an excessive amount of plastic into the gap, causing poor print quality as excess material builds up more and more on each layer. Some will push a smaller-than-commanded strand to try to properly fill the volume.
So, the general advice with small features is to make sure your extrusion width goes into the part's minimum thickness a reasonable number of times.
[Feature size / extrusion width < 2] is BAD
[Feature size / extrusion width = 2] is GOOD
[2 < Feature size / extrusion width < 3] is BAD
[Feature size / extrusion width > 3] is GOOD
Although these will vary somewhat by slicer -- older slicers like Skeinforge tend to have more issues with this than newer slicers. What you should do in practice is check your slicer's print previewer to see whether it is leaving a gap between the strands. Then adjust extrusion width and perimeter/shell count to try to get an intelligent output. There's some trial and error involved.