He's lying again. A little legwork for you:
I checked the Fedex labels at my office--they don't look anything like what he sent you. I called Fedex to check the package (after entering the number in Fedex online with no luck). The Fedex rep said their tracking numbers don't have any letters and that the numeric portion of the number is not long enough. Also, the number he gave you could not be UPS or DHL, both of which have different number schemes than what he sent.
I'd keep on the girlfriend for sure, but politely so she thinks you're the good guy. Grandma may still think he's a peach even after this, but she might cut him off from a little somethin', somethin' if he's been lying to her about it being taken care of.