I faced the same problem in Russia. As a brazilian, I tend to call people by their first names. It's totally ok here, and I felt very uncomfortable having to call my father-in-law by his first name+ochestvo. Actually, it's ok at the beginning, but after a while it sounds really odd. Also for my mother-in-law. Nowadays I call them "Mama" and "Papa", and they love it, but at first I had the same problems, and probably I'll have them again when meting uncles, aunts, cousins, etc.
Also this "Devushka", "Muzhchina", "Molodoi chelovek" sounds VERY impolite to me.