If you are making calls FROM the GATM, the callerID is FIXED at the telco for each particular line. Anything you put in the OLI field will be ignored.
You should check specifically which trunk you are dialing out from and ask the telco to check the callerid associated with that line.
You can also attach a single line phone right to the telco demarc of that trunk and make a test call from there. I will guess you will get the same result you are talking about.
Are you getting this blocked message when you call different numbers or just a specific number? It is possible that when 1 telco passes the call to another, it is dropping the ani along the way.
Of course, I am assuming that you are not putting a *69 in front of your outbound call through the routing feature.