Earlier today Saurik pushed an update for both Cydia and MobileSubstrate, which should now be iOS 4-compatible. To install the updates, just fire up Cydia and do a complete (recommended) upgrade.
I’m running iOS 4 on an iPhone 3GS and Cydia is working just fine. I’ve also installed some tweaks that rely on MobileSubstrate and the new version doesn’t force the device to run in safe mode, unlike many people are reporting on forums and Twitter.
Expect more Cydia compatibility updates coming in the next days.
Cydia version: 1.0.3201-71
MobileSubstrate version: 0.9.3206-1