I know some say your unit tests shouldn't touch the DB but the more full stack tests I have, the better I sleep at night :-))
Unit tests really should be about testing individual bits of logic. Does a single method do the desired thing, and not the undesired thing... Ideally, your data access layer should be interchangeable, ie: use a real database record in production, but use a mock database record for unit tests.
I would consider database access to be an integration test, something that you run periodically but not at every commit.
I wondered if anyone else has run into this problem and found a good strategy to mitigate it.
Shouldn't failling to insert due to FK violation be considered an integration test failure? You may want to beef up your tests to make sure the necessary rows get inserted in the right order. Another option would be to automate the creation of a complete set of test data... using psql to load a dump, or possibly CREATE DATABASE testdbcopy WITH TEMPLATE testdb.
Integration tests can be costly to maintain with little ROI, tread carefully...