Well, we can get a bit of statistics going here.
First, I've got the numbers for how many Alice's there were and the total number of births. I've collected this data for people born from 1920 until 1990. I used a broad range because, remember, the psychic did not hint at any sort of specific relationship. Note, hoever, that excluding the more recent dates will only make these numbers higher, as Alice has declined steadily since the 1920's:
Year......Alices..........Total Female Births
1990......6,435..........19,616,454
1980......7,284..........18,427,957
1970.....11,111..........16,447,641
1960.....26,959..........18,892,808
1950.....52,044..........19,722,134
1940.....72,322..........14,881,731
1930.....78,933..........11,040,309
1920....110,455..........12,395,538
Total....365,543.........131,424,572
That gives us a percentage of 0.278% overall for an "Alice".
Now, how many females would a person possibly know? Using an average family size of 2.5 (probably larger for the time period covered, but we'll use this), that means 1.25 females per family. So, that's 2 grandmothers and (.25*4) 1 great aunt (from both sides of the family, and both grandparents spuses), mother and (.25*2, gotta include Dad's family) .5 aunts, .5 sisters or sisters in law, .25 daughters, .3125 granddaughters, .25 daughters-in-law. Then, we consider close female friends and cousins, which I'm going to back-of-the-evelope at ten over a lifetime that might be signifigant. So, that gives us 15.6625 possible signifigant females. Now, we plug in the cjhances that none of these is named Alice and we get 95.7% (roughly), or 4.3% of knowing an Alice. That works out to a little more than a 1 in 25 chance of getting it right on the first guess. Yeah, the percent is low, but suddenly this doesn't seem that unlikely.
If you start trying to make this calculation more realistic, you'd have to understand that larger families were more common in the first half of the century, and we could actually discount granddaughters and all the data from say 1980 onward. This would actually increase the chances and lower the odds. Also figure that there are probably more than ten or twenty people we would consider signifigant besides immediate family types I listed (I can name twenty at half her age), and the chances increase even more.
So, while a 1/4 percent chance of Alice seems very, very, small...the sheer number of possible targets for the name makes it much less impressive.
Now, I've done the calculation to the best of my ability, but I may have made a mistake in there somewhere, so if someone wants to check it feel free. Also, if you can get a better quantification of the number of possible female relatives that would help. THis is very back-of-the-envelope, but I think it clarifies the point about random chance a bit.