Alltel had it blocked for awhile, then caved in to many angry calls from customers (including me) and unblocked it. I figured it was only a matter of time before another company tried to stop people from using it.
You might want to politely remind them that it's against FCC regulations for them to block access to a public telephone number.
Edit: You can also try 1-888-FREE-411 . It's the same service, alternate number. Alltel never got around to blocking the 888 number.