I just recently upgraded to 5.1 and jailbroken with redsnow. Issue i'm having is when i reboot my phone, most apps do not work. I have to boot tethered to get it all working. I was under the impression that the jailbreak was Un-Tethered, is there currently a fix at this time?

It's tethered for the moment and no fix.

There is a semi-tethered jailbreak but not worth the work. Best option is to tether and boot from redsn0w and wait.