Which version of the iOS 4 firmware did you use? Which version of redsn0w did you use?
There was this problem with earlier iOS 4 jailbreaks and needed an update of Mobile Substrate. But it shouldn't be an issue anymore.
Make sure you're using the official release from Apple and jailbreaking with redsn0w 0.9.5b5-4. Also make sure Cydia updates everything before proceeding with using your device normally.
Current arsenal: iPhone 5S 16GB / 13" Retina Macbook Pro 2.5ghz 8GB ram / iPad 2 WIFI 16GB / Apple TV 2 / Slingbox Solo / Acer Aspire Z5610 touchscreen all-in-one / Acer Aspire netbook
Fallen soldiers: iPhone 5 16GB / iPhone 4S 16GB / iPhone 4 16GB / iPhone 3G 8GB / BlackBerry Pearl 8100 / Motorola L6 SLVR / Nokia 5190, 3390, 8390, 3220 / Ericsson T18z / Mitsubishi G310 / Motorola C333 / Sony Ericsson T237