Check out here first: Can't validate and submit an App to the Mac App Store
Not sure if that'll help. This may seem crude, but did you try restarting your Mac after deleting the expired certificates and submitting again? I wouldn't put it past the age old "cache" problem. It sounds like the same kind of issue that crops up when an expired identity package is in play.