It is possible in linux- I use a Verizon USB727 (Novatel 727) EVDO modem with Mepis 8 in both my car and an HP Mini netbook.
I am not currently using LinuxICE or OpenICE however, and I am not familiar with any specific applications, requirements or quirks in either.
But if you have kppp and a recent kernel, I would expect it to work just fine.