Unable to 'restore' contacts to warranty replaced SamsungS4

I have a replacement phone. Same style, provider and SIM card (AT&T Samsung S4). However, when I attempt to restore my Contacts, avast! cannot connect with my new phone. Any help available would be greatly appreciated.
Thank you,
dcota117

Can you specify more? It can not connect with any message?