Remove doubles isn't removing overlapping vertices
I didn't realize you needed to select vertices for remove doubles to have an effect. To remove doubles on the whole model, select everything with A first (you may need to press it twice if you have anything selected beforehand).