I fixed it. The problem was that in 3CX, under Extensions, under each extensions is a "voicemail section" where you enable voicemail. In there is a PIN field that says "PIN for 3CX Assistant". This is the PIN that is needed when setting up the 3CX Assistant, NOT the 3CX extension password as is used when provisioning phones.
I had to enable voicemail, set the PIN to what what I wanted, and then disable voicemail.
3CX should really move the PIN over to the 3CX Assistant Provisioning field, it doesn't make sense here.