Do we really need the word 'that' here?
Is this sentence correct? 'Everything we need is only a little patience'
No, we don't, Duolingo didn't either. "Tutto ..... bisogno" can be translated word by word: "everything that we have need of" As you see the short version is "All we need" -All- is synonym with -everything- here, so your translation is okay too.
I agree with siebolt. By the way "a little/tiny bit of" would be more accurate, since "pochino" is the diminutive of "poco" => [a] little.
It probably helps if you know the song: http://www.youtube.com/watch?v=tMmX9G8JP38
I'm not sad I didn't get this right, I'm actually happy I was close to getting it right because it's not a simple sentence :)