"Но любой сетевой клиент, при попытке работы с базой данных выдает одну и ту же ошибку: "Длинный формат даты"."

что за клиент, какие технологии он использует? кто разрабатывал, имеется ли исходный код? в каком виде выводится сообщение об ошибке?

"Подскажите, что это может быть?"

что угодно - например, баг в программе, баг в SQL Server, несовместимость программы с версией SQL Server, нарушенные настройки региональных стандартов... 

"как попытаться выяснить в чем проблема?"

отследить на какой операции с какой таблицей возникает ошибка (возможно, запуская программу под отладчиком), понять что не так с этой таблицей / чем она отличается от других, попытаться изменить в ней что-то и посмотреть как это повлияет на программу. 

Может маршрутизатор или фаервол режет пакеты SQL Server'a. Если есть возможность, временно отключите всю фильтрацию трафика между этими сетями и посмотрите что измениться

все же, какие технологии использует клиент? Например, приложение NET Framework или неуправляемое приложение?

как выглядит сообщение об ошибке и какие данные выводятся помимо текста (например, какой-то код ошибки)?

попробуйте запустить программу под отладчиком на проблемной машине и выяснить где именно возникает ошибка

"или не починит то что есть чтоб хотя бы ошибки нормально показывались"

Хорошее замечание. Поскольку это неуправляемое приложение, обработка ошибок производится путем проверки кодов возврата. Если его не проверить, программа продолжит выполнение, и упадет на первой строчке где обработка ошибок таки сделана.

В данном случае, я предполагаю, ошибка ни в каком не в формате даты, а просто программа не может соединиться с сервером. Но проверка ошибки не производится, программа продолжает выполнение и падает на какой-то операции с датой.

Почему не может соединиться? Думаю проблема все-таки в каких-то сетевых настройках: на клиенте, сервере, или маршрутизаторе. Может, в конфигурации BDE. Работает в одной подсети, но не работает между подсетями - уж не Named Pipes ли он пытается использовать?