Certain mesh operations in Blender do not work on non-manifold meshes. In such a case, you may have to manually clean up or fix the mesh to remove the non-manifold elements and fill in correct elements.
First, learn what elements of a mesh cause it to be non-manifold.
Next, ask Blender to show you the non-manifold elements of the mesh. You may have to turn around and zoom into the mesh quite a bit to view such elements which are in obscure corners.
Your work is done when the display at the top shows zero non-manifold vertices, edges and faces!
Tried with: Blender 2.62 and Ubuntu 12.04 LTS