I spent some time trying to setup the DomainKeys/DKIM I did it a couple of times to make sure I copied everything correctly but kept getting "failed" errors. Then, for some reason it clicked "verified." Do you cache this somewhere which prevents changes from showing up immediately.
It can take some time for those changes to propagate to our servers. So it likely just took a little while for that to occur and once it did it verified.