Try turning the SSID on the router from hidden to visible, and then do the actual set up on the phone. I'm using a router with WPA2 and AES (visible), and when I set up the connection on my Hero, the phone recognized the wireless settings just fine with this configuration.
Then try turning your WiFi back to hidden, if you really want to (btw, that has nothing to do with increased security -- I work at Cisco, and our engineers have long joked about how hiding your SSID has no real impact on slowing down hackers).