Well I have no idea ...
What I would propose is this :
- uninstall libgnokii, phonelink, gnokii-gconf
- check that everything is really unisntalled (/usr/bin/phonelink, /usr/lib/libgnokii ...)
- reinstall from the extras repository (only installing phonelink should install everything ...)
- try again