i had a similar issue with my 3G using redsn0w on windows XP. i ended up restoring back to factory 3.0, then re-jailbreaking it with redsn0w on my mac and it's working fine. i really don't know what the problem was, but i think it could have something to do with a bad (yet still functioning) version of either the 3.0 firmware (if you downloaded it from somewhere other than itunes) or your jailbreaking program. either that or it was just a bug with cydia. whatever the case, i suggest restoring back to factory 3.0 and trying to maybe find a diff copy of the software/firmware, they giving it another shot. good luck!