OK there are a couple of things to try;
1. Some folks have found that the phone once paired has a dialogue box asking you to enable PBAP (Phonebook Access Profile). This can be enabled on some handsets in the Bluetooth menu, but other phones just give the dialogue box which can sometimes not be visible due to certain widgets not being coded properly and allowing the dialogue to show. I know of one person who discovered that they had to remove their T-Mobile weather add-on and then discovered the dialogue box had been there all the time. Once PBAP is enabled then the phonebook uploads no problem.
2. I do not have a clue what the max number of contacts is, I am just aware that some owners have cleared their contact lists on their phones out and that this has enabled PB upload. It possibly varies by phone model (ie does the way an Android stores the data differ from Apple or Windows phone in terms of data size?)