Thanks guys. Turns out that it wasn't a normals problem. Somehow all of the edges on most of the mesh got duplicated on top of each other and since some of them are border edges, maya won't let me delete them. So now I have to delete all of the faces until the mesh is smooth again...
"The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable man."
George Bernard Shaw - Man and Superman