Sounds like reversed polygon normals to me. Basically your STL file was not generated correctly. Try running it through NetFabb or MakePrintable and see if that helps.