Did you set the order status to unpublish gift cert? If so to what?
In the same config area, there is a debug. If you set that to yes, the next time it runs a gift cert product and fails it should enter in the text field why it failed. Could try that.
Really not sure, stabbing in the dark here, if you like I can look directly at it if you can send a private message with temp access.