Parrots won't teleport to you if you have to swim in water or use a boat.

After you have tamed a parrot, it will continue to be on your shoulder or teleport to you as long as you are on land.  If you have to use a boat or swim, the parrot enters the water where you did but then stays there, permanently swimming on the spot.