I am aware that cementerio has nothing to do with cemento. It comes from Latin coemeterium which comes from Greek κοιμητήριον, koimeterion = sleeping place, bedroom, dormitory.
I have not found any plausible explanation for the occurrence of the n in the Spanish (and Catalan) spelling. Where does it come from? Is there a more general tendency in Spanish to insert n while adopting Latin words, or is cementerio the only instance?
http://etimologias.dechile.net/?cementerio (the entries authored by the mysterious "Helena" are usually trustable :) ) says (emphasis by me) that
... jamás en la Edad Media las tumbas se cementaban. La forma además alterna con cimenterio desde antiguo. La gente era enterrada directamente en la tierra y los nobles y reyes en pétreos sarcófagos. Nadie ha estudiado realmente a qué se debe esa forma con la nasal.
So the influence of cemento to the spelling and pronunciation of cementerio is not plausible. However, I know that sometimes just a sound similarity of words might influence an alteration of one of them so I am still open to this option.