I tried a different library and that worked. I don't know what was going on with the one I was using. I have the 2 clocks synced to within 15-20ms. Pretty good.
I'm going to try and copy over some of the code from the library into my own sketch so I better understand exactly what it is doing. I'll post my code later to show how I synced the 2 clocks.
For future reference, it seems like the GPS pulse rising is the start of a new second.