I have exactly the same issue and did exactly the same upgrade from 1.1.1 to 1.1.3..and actually searched this forum hoping for an answer.
I seem to recall the issue actually started the day after I did two things :-
1) Synced a lot of media (photos, music and movies) to fill up my iPhone to almost the full 7GB
2) installed a lot of Third party software from installer.app
I am pretty its the second one that causes the slowness, because I have removed all the music/photos/movies from my iphone and i still hv the same sloooooowww response time.
Its really annoying, and I was thinking to either upgrade to 1.1.4 in the hope that it will miralucously be fixed, or downgrade back to 1.1.1 where i distinctly remember it being significantly faster....
Help anyone????