I really appreciate your help!!!
The theory I heard is that
Saul changed his name to
Paul when he disembarked in Greece to spread his new religion. The reason he changed his name is that the word saulos (as
Saul would be if were Hellenized) had somewhat silly undertones: it is related to the verb "sauloproktiao", which means "walk in a swaggering way, so as to make the hinder parts sway to and fro" (
http://www.perseus.tufts.edu/cgi-bin/ptext?doc=Perseus%3Atext%3A1999.04.0057%3Aentry%3D%2393442) -- which is certainly against the Judeochristian spirit!