When iPhone is jailbroken and software-unlocked, sometimes the iPhone will have issues with apps that rely on push notifications. This is because the iPhone is "hacktivated" rather than activated with an AT&T sim card. In order to connect to Youtube and fix the push notification issue, you will need to install an app from Cydia.
Go to Cydia->Manage->Sources and add source cmdshft.ipwn.me/apt/
Search for Push Doctor or Youtube fix in the source and install the app through Cydia
Now reboot the iPhone and you are done
This has been tested working on iPhone 3G and iPhone 3GS