Thank you so much for your reply!
Looking at the 1900 Federal Census, it says that Catherine M. Messina was married to Antonio Messina (Messina being Sicilian in origin). It says Catherine's father was born in Greece. The 1920 census says the same (though it spells her name with a K in that one, but the family is still the same), and says she was born January 1870. A cousin I met here says her father's name is Frank and her maiden name was Pararo/Parara, although it is documented on censuses as varying in the many ways I noted. In internet searches I've done, you're definitely right that Perera seems Portuguese in origin... so this remains a total mystery for me!