I just received the same error - is this a bug?
How did you install the bundle? Just copying it to the /deploy folder would not be sufficient, as you need some additional bundles to provide the OSGi CXF support. You should be OK if you first install the 'cxf-osgi' feature and then deploy the bundle.
If you take a look at the README.TXT file that comes with this example, you'll notice that it recommends installing the example with a features install examples-cxf-osgi command, which will do exactly the same thing: first install the required features and then add the bundle.
Does this solve your problem?