FYI - I came across the following entry in Wikipedia regarding the eight most popular/common surnames in Lithuania.
I justed started researching my Paulauskas line and see that the surname is the eighth most common surname in Lithuania so it will be tough trying to find the right one.http://en.wikipedia.org/wiki/List_of_most_common_surnames#Li
Most popular Lithuanian surnames 2007:
# For men For women
1 Kazlauskas Kazlauskienė
2 Stankevičius Stankevičienė
3 Jankauskas Jankauskienė
4 Petrauskas Petrauskienė
5 Vasiliauskas Vasiliauskienė
6 Žukauskas Žukauskienė
7 Paulauskas Paulauskienė
8 Urbonas Urbonienė
It's not surprising that the married female spellings (i.e., IENE ending) of the family surnames spellings align in the same rank order.
My sympathies go out to those researching the Kazlauskas surname and the challenges they face.