That makes sense. I am not sure what the reasons are for all of the delays around the Nuvifone, but I suspect much of it has to do with trying to develop a device and customize Linux for the device at the same time. It takes a lot of resources to make a consumer device that has your own custom OS on it.
If you don't believe me, look at Palm. PalmOS versions 1-4 had a kernel written by a third party. Even OS5 was the old kernel surrounded by basically a host OS that could enhance some operations of the device. For the most part, you couldn't write a native PalmOS 5 app. You wrote for 4.x and the Palm Application Compatibility Environment (PACE) ran the app for you, and PACE was basically OS 4.x. When they tried to make OS5 a native operating environment via OS6, it was a failure. Not a single device shipped with it. Palm didn't even bother. They then started a custom Linux version and eventually wound up with WebOS, which is shipping with the Pre. This isn't to fault Palm, it is to show you that even a company that has been making consumer devices for a decade can struggle with writing their own OS.
I suspect Garmin threw in the towel on their flavor of Linux and opted to take an off-the-shelf OS like Android and Windows Mobile and add their own UI tweaks, custom features and drivers, leaving the heavy lifting to Google and Microsoft employees.
No devices have yet been announced, but I bet when they are, they will not suffer from 18-24 month delays.