Are you sure Recovery Mode didn't pop out with the iTunes logo. It had to. In other words from my own Experience try exactly this:
1. Have your iDevice not connected to anything.
2. Hold the Power button + Home button for about 10 seconds.
3. After the 10 seconds, release your finger from the Power button BUT you MUST keep holding the Home button with out letting go of it.
4. While holding the Home button connect it to iTunes, even if the iTunes logo is not on screen and your screen is black.
5. In iTunes, a message will display telling what to do after.
Good luck. Let me know if you need more help!
Sent from my iPhone 4S