Was May 3rd the day you transferred the domain or moved hosts? I was thinking maybe there could be some issues related to that? Especially if the domain transfer occurred around the time one gmail server was on the new record while their spam detector server was referencing the old one?
I think most people use "v=spf1 mx a -all". Not sure what the ~ gets, but it might support some forms of older SPF. In any event, it's working fine recently, just that one email from the 3rd that I missed.
EDIT: You could also try adding
IN SPF "v=spf1 a mx -all"
RFC 4408 recommends both TXT and SPF if possible, anyway.