Annoying shading problem after joining objects :(

I am currently modelling a sword, its made up of different pieces but when i try to join them all, the shading becomes all dodgy…

if i switch it to flat shading, the problem disappears, but i really need to use the smooth shading option… how can i fix it?

Remove any faces inside the mesh, any double vertices (select all vertices and W / remove doubles), then recalculate face normals (select all faces and Ctrl+N)