Saved an MX record but mail still bounces

Added the correct MX for my new mail host, saved it, and inbound mail is still bouncing with 'no route to host'. When I dig the domain I can see two MX records — mine and an old one from before that I thought I'd deleted. The old record didn't actually delete when I clicked remove.