He, he, he! Booklady, Paloma is only a fairly common name in Madrid, since 'La Virgen de la Paloma' is one of the two patron saints of this city (the other one is the very "arabic-ish" Almudena, also a female name); outside of Madrid is pretty unusual, when I was growing up in Zaragoza, I attended a school with 1800 students and there were only two other Palomas besides me (Of course there were countless girls named Pilar!!!) In the Basque Country, there are some girls named Usue (not 100% sure about the spelling), that's paloma (dove) in Basque; and it would be Coloma (or Colomba) in 'Catalán'.
The same names aren't the most popular ones all the time, some become very "in" sometimes....when I was little I had lots of little friends called Eva and Marta, Beatriz, Sandra (Alejandra) or Susana....more recently, there seem to be a good number of Andreas, Ineses, Carlotas and Lucías being born, as for boys, I hear Daniel and Javier a lot these days, and Manuel, Jose, Juan, Carlos, Pablo, Luis, Francisco or Nacho (Ignacio) are of course all-time favourites.
Now, the name Maria comes usually as a "nombre compuesto' (compound name¿?), like Maria Isabel (Maribel), Maria José, Maria del Carmen (Maricarmen or Mamen),...also José (also known as Pepe or Pepito) becomes very often: José Miguel, José Luis, José Maria (Aznar
).
P.S.: Thanks Eduardo for your comments! (BTW, I guess we call pigeons "pichones').
Martine, Maria de la Concepción is indeed a quite common name! (though we call them Conchas or Conchitas, and please don't ask me the meaning of concha for Argentinians! :o ), but not only that, Inmaculada (immaculate) is also very common!!! Also, I believe Peio is Basque for Pedro (Peter).