My fiancée had a jailbroken 1.1.1 phone, not unlocked. A couple of days ago the phone started acting weird (no calls on standby, no wi-fi, no bluetooth, and the phone's time is completely fucked up). Did a restore, didn't fix the problem. Called Apple, and as soon as I mentioned "No Wi-Fi, no bluetooth, no calls," they said it was defective and told me to send it back (And even gave me a free AppleCare Loaner).

My question - does restoring erase all remnants of applications that were installed on the phone?

yes, it's like formatting