After some trial and error, I had both phone and edge/3G working briefly. Some things I've learned:
-- Start from scratch: Restore system to clean 3.0 via iTunes.
-- Run redsn0w immediately, without allowing rebooting phone to sync with iTunes.
-- Only install Cydia. Icy install breaks Cydia.
-- Install ultrasn0w (via Cydia) before doing anything else.
-- Then wait a bit. I had "no service" for around 6 hrs, then gave up, did some work and checked back 10 hrs after ultrasn0w reboot. Found phone, edge, 3G working and stable.
-- Don't restore the iPhone from backup in iTunes. Use as "new phone." You lose your SMS log, but the restore broke my edge/3G access both times I tried it.
My guess is that ultrasn0w relies on a loophole that is some manner of "race condition" or sporadic vulnerability.
Hopefully the devs will release an update that is more stable. But for now, the steps above may work for you as well.