That sounds like a problem indeed.

Do you think it would be a problem to keep it that way and add your device to the list of PINs[1] or are there many other devices that could have this problem?

Your device is the first one I encounter that's got a non-numerical PIN by default.

[1]: http://git.gnome.org/browse/gnome-bluetooth/tree/wizard/pin-code-database.xml

Note that to add your device to the database, I'd need the output of:
hcitool inq "bluetooth address"
and you can get the bluetooth address by running:
hcitool scan
when the device is visible

Usually devices use numerical PINs like 0000, 1111, 1234, but this is the very first that I saw as shown in device manual:

www.navman.com/docs/manuals/navman-4100-4420-4470-manual-en.pdf

I used this GPS receiver few years ago with PDA and don't remember such problems.

I don't know if other vendors have devices with non-numerical PIN devices, but I think it should be an interesting feature. 



$ hcitool scan
Scanning ...
    00:0C:A5:00:xx:yy    NAVMAN GPS ONE

$ sdptool search SP
....

Searching for SP on 00:0C:A5:00:xx:yy ...
Service Name: NAVMAN GPS
Service RecHandle: 0x10000
Service Class ID List:
  "Serial Port" (0x1101)
Protocol Descriptor List:
  "L2CAP" (0x0100)
  "RFCOMM" (0x0003)
    Channel: 1

Thanks for all!

I also need the "hcitool inq" output as requested.

clock offset: 0x5d65    class: 0x011f10

You can add those 2 lines:
        <!-- https://bugzilla.gnome.org/show_bug.cgi?id=613698 -->
        <device oui="00:0C:A5:" name="NAVMAN GPS ONE" pin="NAVMAN"/>
to /usr/share/gnome-bluetooth/pin-code-database.xml

(insert it at the end of the GPS devices section)

and it should detect the PIN needed automatically.

commit 2a10ca4aa9c879e03ce7bbcfa7a340fe7685e0ba
Author: Bastien Nocera <hadess@hadess.net>
Date:   Thu Mar 25 00:43:21 2010 +0000

    Add PIN code for Navman GPS One

Done and works fine.