After some tinkering on my 10.8.3, I discovered It's not just the firewall that's causing the trouble. It's PF itself. While PF is enabled, ipfw forwarding rules (which is what sshuttle sets up) silently stop working, so as a result, sshuttle claims it's working perfectly, but nothing will be redirected through.
The firewall uses PF internally, setting up rules at the `com.apple/250.ApplicationFirewall/*` anchor, but it's not the only one. Internet Sharing, as well as AirDrop, use (and enable) PF as well, so bear in mind that using any of those will prevent forwarding from working while they are running.
I think this would definitely be worth putting in the Known Bugs section, but ultimately the application should be made to generate PF redirect rules instead. However, I haven't had success yet in getting those to work.
PS: yes I do get kernel panics too (10.8.3 on 2011 MBA), for what it's worth. Probably about once a day so far. I guess I'll try to get PF to do the forwarding instead.