Hmm...
Have you thought about starting with sit-ups? Often sore shoulders are as much due to a weak core as to a weak upper body. You might also get your bike fit double checked.
Though as long as you start slow, I don't think there would be any harm in doing some upper body work too - just do less than you think you are capable of for the first 2 weeks or so ...