That is atrocious behaviour for a hosting company. Obviously they did not check whether anyone was using it because they didn't know you were. It is possible to run both Zend and ionCube on the same server, so there is no reason why they should withdraw support for ionCube. Depending on how the server is configured, it might also be possible to install ionCube just on your account, and not server-wide (you can use the wizard script file that comes with the ionCube loaders to check whether that is possible or not).
Unfortunately, it is not possible to run nBill without ionCube, so unless your hosting company will allow you to get ionCube running on your account, the only other option is to move to another host.