I was at CTIA this year looking for Wimax enabled devices and release schedules, here are some relevant links from people I saw on the show floor:
Go to the part about Wimax Phones. There are also Wimax video IP phones and wimax based surveillance systems shown there, see a product announcement here from Feb.
I don't see details on their site, but the handset I have a flyer for was called the Sting, and was dual mode Wimax/GSM.
Also saw one called the wiofone: http://www.wimax.com/commentary/blog/blog-2008/wimax-blog-wimax-desktop-phone
Placeholder website here: http://wioline.com/
Samsung was also present displaying a number of devices with embedded Wimax chipsets in them, intended to use VoIP as part of the connectivity, such as the PDA (SCH-M830 and M8200), an UMPC or 2 (all of which were Windows based devices), and some standard laptops with wimax chipsets in them.
It's a chicken-and-egg problem still, since the devices will become more common when there's more coverage, more markets, and more possible subscribers, but people will fund the growth of the network when there are devices available which use it. It seems pretty obvious from investments that Intel/Motorola et al are both trying hard to lock in a future where many devices will have embedded wimax chipsets simply included as bluetooth and wifi chipsets are today. And not just laptops, but cars, washing machines, refrigerators, anything that would benefit from network access.
Man I wish I had mod points...