Ни с одним из российских высокопоставленных чиновников у Эдуарда Шеварднадзе не сложилось столь неприязненных отношений, как с директором ФПС Андреем Николаевым.
Первый раз они поссорились летом 1995 года, когда Николаев без предварительного согласования с президентом Грузии встретился в Сочи с лидером Абхазии Владиславом Ардзинбой. Из Сочи директор ФПС вылетел в Тбилиси. В самолете, узнав о негативной оценке президентом Грузии своей встречи, Николаев приказал изменить курс на Москву.
За прошедшие два года Николаев несколько раз встречался в Тбилиси с Шеварднадзе. И каждый раз переговоры шли крайне трудно. К личной неприязни добавились и серьезные разногласия по вопросу об охране грузино-турецкой границы. Как известно, грузинский парламент готовит закон "Об охране государственной границы", предусматривающий поэтапный вывод российских погранвойск с турецкой границы, что противоречит российским интересам, которые отстаивает Николаев.