When the device does not show up in NetworkManager, can you run "lshal" from a terminal and look through the output for the block that describes the "ttyUSB0" device?  If that block *is* present, does it contain the "modem.command_sets" property?  If you're unsure, just attach the entire lshal output and I can figure out these answers.

Here's the lshal bit, I hope it's the right one. It doesn't seem to have that property.

udi = '/org/freedesktop/Hal/devices/usb_device_1d6b_1_0000_00_13_3_if0_0_serial_usb_0'
  info.capabilities = {'serial', 'pda'} (string list)
  info.category = 'serial'  (string)
  info.parent = '/org/freedesktop/Hal/devices/usb_device_1d6b_1_0000_00_13_3_if0_0'  (string)
  info.product = 'Pocket PC PDA'  (string)
  info.subsystem = 'tty'  (string)
  info.udi = '/org/freedesktop/Hal/devices/usb_device_1d6b_1_0000_00_13_3_if0_0_serial_usb_0'  (string)
  linux.device_file = '/dev/ttyUSB0'  (string)
  linux.hotplug_type = 2  (0x2)  (int)
  linux.subsystem = 'tty'  (string)
  linux.sysfs_path = '/sys/devices/pci0000:00/0000:00:13.3/usb5/5-1/5-1:1.0/ttyUSB0/tty/ttyUSB0'  (string)
  pda.platform = 'pocketpc'  (string)
  pda.pocketpc.hotsync_interface = '/dev/ttyUSB0'  (string)
  serial.device = '/dev/ttyUSB0'  (string)
  serial.originating_device = '/org/freedesktop/Hal/devices/usb_device_1d6b_1_0000_00_13_3_if0_0'  (string)
  serial.port = 0  (0x0)  (int)
  serial.type = 'usb'  (string)


Other bits:

# lsusb | grep Phone
Bus 005 Device 018: ID 0bb4:00cf High Tech Computer Corp. SPV C500 Smart Phone


Feb  7 19:03:10 hodge kernel: usb 5-1: new full speed USB device using ohci_hcd and address 18
Feb  7 19:03:10 hodge kernel: usb 5-1: configuration #1 chosen from 1 choice
Feb  7 19:03:10 hodge kernel: ipaq 5-1:1.0: PocketPC PDA converter detected
Feb  7 19:03:10 hodge kernel: usb 5-1: PocketPC PDA converter now attached to ttyUSB0
Feb  7 19:03:10 hodge kernel: usb 5-1: New USB device found, idVendor=0bb4, idProduct=00cf
Feb  7 19:03:10 hodge kernel: usb 5-1: New USB device strings: Mfr=1, Product=2, SerialNumber=0
Feb  7 19:03:10 hodge kernel: usb 5-1: Product: Generic Serial
Feb  7 19:03:10 hodge kernel: usb 5-1: Manufacturer: HTC

yeah, so if it doesn't have that property, NetworkManager won't recognize it.  This property is assigned based on the stuff in /usr/share/hal/fdi/information/10freedesktop/10-modem.fdi.  When the phone is plugged in, can you attach the output of "/sbin/lsusb -v" so we can see if it's a cdc-acm driven generic modem or whether it needs tagging in the fdi file?

The question is, why does that property not always appear unless I restart NetworkManager? It's repeatable: if I restart NM in between unplugging and replugging the phone, the property is always there. If I don't, it's often not.

Here is what's normally in lshal, i.e. with the property:
udi = '/org/freedesktop/Hal/devices/usb_device_bb4_cf_noserial_if0_serial_usb_0'
  info.capabilities = {'serial', 'modem', 'pda'} (string list)
  info.category = 'serial'  (string)
  info.parent = '/org/freedesktop/Hal/devices/usb_device_bb4_cf_noserial_if0'  (string)
  info.product = 'Pocket PC PDA'  (string)
  info.subsystem = 'tty'  (string)
  info.udi = '/org/freedesktop/Hal/devices/usb_device_bb4_cf_noserial_if0_serial_usb_0'  (string)
  linux.device_file = '/dev/ttyUSB0'  (string)
  linux.hotplug_type = 2  (0x2)  (int)
  linux.subsystem = 'tty'  (string)
  linux.sysfs_path = '/sys/devices/pci0000:00/0000:00:13.2/usb4/4-1/4-1:1.0/ttyUSB0/tty/ttyUSB0'  (string)
  modem.command_sets = {'IS-707-A'} (string list)
  pda.platform = 'pocketpc'  (string)
  pda.pocketpc.hotsync_interface = '/dev/ttyUSB0'  (string)
  serial.device = '/dev/ttyUSB0'  (string)
  serial.originating_device = '/org/freedesktop/Hal/devices/usb_device_bb4_cf_noserial_if0'  (string)
  serial.port = 0  (0x0)  (int)
  serial.type = 'usb'  (string)

Here's the lsusb -v bit. The phone is wrongly identified as concerns its model and wrongly identified as CDMA when it's GSM; I filed a bug about it at freedesktop.org but it was closed (I was told there was a generic solution coming that would make it irrelevant):

Bus 004 Device 005: ID 0bb4:00cf High Tech Computer Corp. SPV C500 Smart Phone
Device Descriptor:
  bLength                18
  bDescriptorType         1
  bcdUSB               2.00
  bDeviceClass           32
  bDeviceSubClass         0
  bDeviceProtocol         0
  bMaxPacketSize0        64
  idVendor           0x0bb4 High Tech Computer Corp.
  idProduct          0x00cf SPV C500 Smart Phone
  bcdDevice            0.90
  iManufacturer           1 HTC
  iProduct                2 Generic Serial
  iSerial                 0
  bNumConfigurations      1
  Configuration Descriptor:
    bLength                 9
    bDescriptorType         2
    wTotalLength           39
    bNumInterfaces          1
    bConfigurationValue     1
    iConfiguration          0
    bmAttributes         0xc0
      Self Powered
    MaxPower              100mA
    Interface Descriptor:
      bLength                 9
      bDescriptorType         4
      bInterfaceNumber        0
      bAlternateSetting       0
      bNumEndpoints           3
      bInterfaceClass         2 Communications
      bInterfaceSubClass    255
      bInterfaceProtocol    255
      iInterface              0
      Endpoint Descriptor:
        bLength                 7
        bDescriptorType         5
        bEndpointAddress     0x81  EP 1 IN
        bmAttributes            2
          Transfer Type            Bulk
          Synch Type               None
          Usage Type               Data
        wMaxPacketSize     0x0040  1x 64 bytes
        bInterval               0
      Endpoint Descriptor:
        bLength                 7
        bDescriptorType         5
        bEndpointAddress     0x02  EP 2 OUT
        bmAttributes            2
          Transfer Type            Bulk
          Synch Type               None
          Usage Type               Data
        wMaxPacketSize     0x0040  1x 64 bytes
        bInterval               0
      Endpoint Descriptor:
        bLength                 7
        bDescriptorType         5
        bEndpointAddress     0x83  EP 3 IN
        bmAttributes            3
          Transfer Type            Interrupt
          Synch Type               None
          Usage Type               Data
        wMaxPacketSize     0x0040  1x 64 bytes
        bInterval              32
Device Status:     0x0000
  (Bus Powered)


In case it's of relevance, I have hal-0.5.11-2.fc9.x86_64

Ah, it's driven by the 'ipaq' driver.  Not cdc-acm.  Didn't know about that driver.

NM shouldn't have anything to do with whether or not it gets the HAL "gsm" or "cdma" properties; my guess is that it's more a case of timing between HAL, udev, and the kernel driver when the tty device shows up.

It shouldn't have anything to do with NM... but the weird thing is that 100% of the time, restarting NetworkManager always prevents the bug from occurring...

This message is a reminder that Fedora 9 is nearing its end of life.
Approximately 30 (thirty) days from now Fedora will stop maintaining
and issuing updates for Fedora 9.  It is Fedora's policy to close all
bug reports from releases that are no longer maintained.  At that time
this bug will be closed as WONTFIX if it remains open with a Fedora 
'version' of '9'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version prior to Fedora 9's end of life.

Bug Reporter: Thank you for reporting this issue and we are sorry that 
we may not be able to fix it before Fedora 9 is end of life.  If you 
would still like to see this bug fixed and are able to reproduce it 
against a later version of Fedora please change the 'version' of this 
bug to the applicable version.  If you are unable to change the version, 
please add a comment here and someone will do it for you.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events.  Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.

The process we are following is described here: 
http://fedoraproject.org/wiki/BugZappers/HouseKeeping

Fedora 9 changed to end-of-life (EOL) status on 2009-07-10. Fedora 9 is 
no longer maintained, which means that it will not receive any further 
security or bug fix updates. As a result we are closing this bug.

If you can reproduce this bug against a currently maintained version of 
Fedora please feel free to reopen this bug against that version.

Thank you for reporting this bug and we are sorry it could not be fixed.