How's your internet connectivity? Are you behind a strict firewall on your router?
Also, what is the exact wording of the message? Try tapping the Sources button at the bottom of Installer and tap 'Refresh' on the top-left. See if that will allow you to install stuff.
PS: If you have any iTunes Store DRM-protected stuff, you'll want to jailbreak to 1.1.2 and then do the 1.1.3 update via installer. Going from 1.1.1 to 1.1.3 won't allow you to play any DRM'd stuff.
Good luck!