Perhaps there was another way, but researching via the Internet didn’t turn any up. I’d be happy if someone was able to post something in the comments to help anyone in the future, but I believe this highlights one of the big problems with iCloud: there’s no way to really get at your data in the cloud. I would have loved being able to go to icloud.com, log in, and click a button to restore my contacts to where they were at 10:38am, before I accidentally deleted them all and gave myself three hours of unnecessary work.
This is the sort of situation where the cloud should be an advantage. iCloud should have a Restore Contacts feature like Gmail’s. In fact, perhaps it would make more sense to sync one’s Mac and iPhone with Google rather than iCloud.