We route our 800 #s via IDC. So, in your case you can see if you already have some IDC tables or you would change an existing table. So, your 800 number IDC entry would look like this:
LD 49
chg
idc
0
800-222-1111 8000
This would route 800-222-1111 to internal number of 8000 (usually your ACD group).
If you are not sure you can use prt instead of chg to print your tables they are usually in the lower range like 0 thru 100.
I agree with GHTROUT that it could be their calls that are not routing versus your incoming not routing as we would assume your 800 number is already routable unless it happens to be a new number you are trying to set up.