Well, I will be honest, I have a lot to learn about HDR myself. I wanted to get a feel for how it's done and see the originals that made up this image, and what software is used to get certain results.
Personally, I think it's kind of a good thing that this image does not look 'overdone.' I like the final image much better than it's counterparts, although the one thing I will suggest is that you take an extra shot or two in addition to your bracketed exposures to expose for the really dark or shadowed areas (even though it is a night shot), so you will not have noisy areas where those dark areas lie.
Obviously, the same ideas of composition apply to night photography and once you apply them, I think you will get some really great images! Again, this is coming from someone not very well versed in HDR, so you can take it with a grain of salt if you wish. I will be getting Photomatix, and maybe I will share my results as well.
Thanks for posting the originals!