Unless the phones were first discovered locally than moved out to the remote site - it sounds like connectivity to the remote site is good as the problem description below indicates.
Things to look at: 1) Is the NBX setup for Standard IP or IP on the Fly (vs Ethernet) 2) Are the phones already discovered (auto-discovery enabled) 3) Is there enough Group 2 licenses available for the new phones