Everyone is related to everyone if you go back far enough. So not that shocking.
If you go back n generations then you have 2^n ancestors (assuming zero cross-genealogical breeding). So if you go back 2^11 generations, you will have 2,048 ancestors. And the other person has 2,048 ancestors in that generation. Plus there only needs to be one overlap for you to be "related". Factor into that also the relatively smaller populations compared to today. On top of which they probably went through a ton of other peoples' genealogy to find someone notable that was related to Obama.
Also the fact that due to wealth, genes, and educational chances someone who is a prominent member of society is much more likely to have offspring who are also prominent members of society.
So coincidence, yes. Astoundingly improbable coincidence, no.