I came across your question as I was setting up DKIM in our own environment. Now that I have it working (in my test environment), I wanted to respond to your question.
There are two packages (that I know of) that can be used for implementing DKIM, both of which are, as of this writing, available in the EPEL (yum) package repositories:
I first started with dkim-milter, simply because I didn't know any better and that was the first thing I tried. After talking with some folks in the #Postfix IRC channel on Freenode, I was pointed to OpenDKIM.
dkim-milter is still available, but it hasn't been updated since 2011, and apparently is no longer maintained. OpenDKIM is a fork of dkim-milter, and from what I can tell, is the better approach.
Moral of story: I recommend OpenDKIM.
Now, you didn't tell us what you were using to sign your messages. If you still need help, then respond (or edit your question) and tell us if you're using OpenDKIM or dkim-milter (or something else).
Now that this is out of the way, using OpenDKIM, there's a command you can run,
opendkim-testkey which allows you to test the key and see if its valid or not, even before you even send test messages.
I was having the exact same issue that you were, although I was able to get my key to validate with opendkim-testkey. Turns out that my issue was because I had set the "Selector" identifier in /etc/opendkim.conf to "mail01.private" when in fact my selector was simply named "mail01." The key file was named "mail01.private" but the filter itself was just "mail01" - once I made that change, the message headers in Google showed that DKIM passed.
Hope this helps!