My outbound caller ID is only sending the 4 digit extension of the calling phone.
In CCM (5.1.2) in the external phone number mask I have the full 10 digit number.
I believe that by 'check your gateway' they meant to check your callmanager gateway configs. Typically, you wouldn't alter your callid from the actual gateway. Typically, you'd handle that from callmanager.
Apart from the external mask on each phone line, you can alter the mask at several other levels: gateway, route list, and route patterns.
Each higher level overrides the previous level settings (so gateway trumps route list, route list trumps route patterns, route patterns trump phone lines, and the actual gateway translation rules or whatever override callmanager). From the hip, my guess is that the "Use Calling Party's External Phone Number Mask" checkbox on your route pattern(s) is not checked.