Your anecdote is valid, but there are A LOT of PDA's out there. Many of them have a grid of icons layout. For instance, consider the Sharp PDA's GUI -- it's a grid of rectangular icons broken up into pages (albeit with named tabs).
That being said, there may be something unique to Apple's patent, but on its face, "grid of icons" as a UI pattern predates the iPhone considerably.