I've found a solution to this. The steps are
1. Recompile the C++ Service.
2. Locate the TLB file for the service. It will be in the same place as the OBJ files for the project.
3. Use TLBIMP
to generate a .Net DLL for the service.
4. Register the DLL using REGASM
5. Re-open the C# project and re-build. It will now get the updated interface definition.