Wietse's advice is the first thing I would try: Eliminate anything that modifies your message after signing. The most common signature failure in our analysis apart from DNS setup problems has been a message that was malformed in the first place, so when it gets "fixed" someplace downstream, the signatures break. Interestingly, a malformed "To:" field was the biggest culprit.
I suggest trying again with OpenDKIM (http://www.opendkim.org). The dkim-milter package has been unmaintained for a couple of years now. It lives on under the new name, with lots of bug fixes and new features since dkim-milter's final release. If it still fails, you can get some debugging help on the OpenDKIM support lists, including some tips for figuring out what's getting changed after signing and (possibly) where and why. -MSK
