ok, i think i found the trick!
after you gave me your data sample set, my first thought was: What a crap! ;)
Your sample consists of 71 single lines, which partly overlap and have some tiny offsets as well.
i guessed that GRASS would be the way to go, and ... tada .. it is
so, this is your line data labeled with its feature ids.
If you know how to do it, enable the GRASS-Plugin, create a new mapset and location and such irritating stuff.
Once this is done, follow the directions from my first answer about importing the loaded layer into grass.
Because you have some small offsets, i would e.g. set the threshold for the snapping to 10 meters (or whatever your CRS is, you sent it without prj)
Besides the threshold, you need to check the checkbox above telling about converting lines to boundaries.
After running the command, you can view the resulting line layer, which now has only 36 features.
I didn't get it in the first run and it's not really obvious, but a polygon layer was created within GRASS at the same time.
To get this, go to the GRASS-Toolbox -> "Browser"-Tab ->
select your mapset and hit the blue Refresh-Button ->
expand the folder and go into "vector" ->
mark the polygon sublayer and click the "Add selected map to canvas"-Button.
Your fresh polygons are now in the QGIS canvas.
Check the CRS of the layer, cause QGIS/GRASS-Plugin tend to play tricks on you there (in case it is not the right CRS, just change it to that).
Finally, save the layer as shapefile, and you are ready for the rest of your adventure.
At least this sample looks really clean now, but i don't know about the rest of your dataset, so experimenting with values might still be necessary.