The phrase is taken from the field of National Hunt racing...ie horses running "over the sticks". Some such races have fences...ie quite wide and substantial obstacles, as in the Grand National...and others have hurdles...ie thin tree-branches woven together and placed across the course. The latter are easily knocked over. Accordingly, if a horse "falls at the first hurdle", it suggests that it never really had much chance of success.
In the field of human relationships, things might progress well until the first 'problem' arises and that may put an end to the matter. Just like the horse, the people are unable to surmount the very first difficulty placed in their way.