I wasn't lucky the 1st time I visited the Vizier either, even after throwing several coins into the water in Indinera Woods by the sign.
So I returned to the area and threw 100 gold into the water, one at a time.
Then returned to Vizier in the Cape of Ultai, wore my ring of luck and spoke to him again. This time I was lucky enough.

Million to One chances happen 9 times out of 10. Terry Pratchett