I noticed the same thing and thought it was a bug. I tried a restore but still small thumbnails. Odd thing is my friend has 3.1 and says the pictures are still big on his 3GS.
When you add people with contacts via software on your computer (such as Address Book) and pick pics for the contacts in the software, you get the smaller pictures. If you add them from your iPhone you get the large picture. So, if you have the photos synced to your iPhone, just choose the photos again for each of your contacts that you want photos for.