In the picture:
There are 4 shadows/discoloration caused by the subsurface. What did I do wrong? I’ve removed doubles, there weren’t any, recalculated normals, and checked for internal lines/faces. What do I try next?
I guess upload your blend file.
Oh and welcome to BlenderArtists 
Go into face select mode and find and delete the internal face thats there. Also, try to do something about those triangles if your planning to use subsurf.
i’ve tried to fix up your model a little. you should try and keep everything quads, and try not to have a lot of edges meeting at one vertex if your using subsurf.
Attachments
ship.blend (353 KB)
Your problem had something to do with creasing. Don’t know how you did it lol but anyway I fixed it without adding any more verts (like in Blazr’s fix.)
Either will work.
Cheers dude, and happy Blending!
Attachments
Robo3Dguy-ship.blend (330 KB)
Thank you, what exactly did you do to fix it? Did you just delete surrounding vertexes and then replace them? Deleting the internal face (just one?) didn’t fix the ones on the left… Blazr’s fix I think is the best as it also solved the ones on the right. Once again thank you all.