Fixing non manifold-ness

I can’t decimate my mesh because Blender thinks it is non manifold. Is there a way to tell it to “fix” the non manifold edges (I guess by deleting one of the triangles)?

I found this:
http://www.blender3d.it/index.php?filename=lab/nonmanifold.html

But it has been running for hours. It’s a pretty high poly count model, but it seems like this should be built into Blender anyway.

Any suggestions?

Thanks,
Dave