I finally managed to get my phone connected to my linux boxes with Gnokii, both using a Nokia CA-42 cable and using a bluetooth dongle.
Using a CA-42 cable all thats needed is to run

modprobe usbserial vendor=0x0421 product=0x0802

before attaching the phone. That will resultin a /dev/ttyUSB0 device appearing when the phone is attached.
Gnokii can then connect to the phone with this setup in ~/.gnokiirc:

[global]
port = /dev/ttyUSB0
model = AT

Once connected, the phone is found:

$ gnokii --identify
GNOKII Version 0.6.8
IMEI         : 355687309745842
Manufacturer : Nokia
Model        : Nokia 6021
Revision     : V 03.83

and I can remote control the phone. Not everything appears to work, though. I can read and send SMS messages, and I can get and set contact information. I haven’t managed to get gnokii to read calendar setting or logos or ringtones.
I managed to get it to connect via bluetooth too. First I had to pair the phone with the computer from the phone, and allow access without confirmation.
When that was done, I could connect to the phone with gnokii:

$ gnokii --identify
GNOKII Version 0.6.8
IMEI         : 355687309745842
Manufacturer : Nokia
Model        : RM-94
Revision     : V 03.83

Its the same phone, even though it is identified differently.
In this case the ~/.gnokiirc stanza is:

[global]
port = 00:13:70:0E:D6:7D
model = 6510
connection = bluetooth