My experience was a tad different, but then I'm using an iPhone5 and not an Android device. However, what I learned might be helpful to others. The process was simple: follow the LEAF prompts after the iPhone is paired with the car. Very easy, but some interesting things occurred:
1- the LEAF can only store 300 entries. If your address book is larger, it will stop uploading when it reaches 300.
2- Since you can pair 5 bluetooth devices, per conversation with a Nissan LEAF support person, you can actually upload 1500 entries, 300 per device. Unfortunately, you cannot combine this maximum in any useful way. And, you can only use one set of 300 from whichever device is paired at the time.
3- In my iPhone Contacts application I have a couple thousand entries sync'd across multiple other devices. To weed this down to only 300, I created a subgroup of entries, which I (so cleverly, I know) called "LEAF." I copied the entries into this group that I'm most likely to use in the car. Then, after you've paired the phone to the car, open the Contacts application on the iPhone, open the "LEAF" subgroup, and THEN upload the entries. Worked quickly, got everything, and life is better once again.