Yeah jailbreak doesn't replace the logo by default, you will have to do that manually (you know you are replacing the logo by check a box in redsnow) before the logo can change. I still have the apple logo on my jailbreak iPhone 4.
Our methods sticky explains all the methods, but as you already know redsn0w tethered is the only way to go. And the logo is disabled by default in this version for reasons to do with IOS5 beta...