You have not been added to the Blackberry Enterprise Server error - no enterprise data plan

I was trying to add a new Blackberry Curve to a Blackberry Professional Server (predecessor to the Blackberry Express Server) but it would not connect to the server. I entered the email address and wireless activation key but it just sat on "Contacting Server..." for several minutes.  Then I would get an error message that read "You have not yet been added to the Blackberry Enterprise Server. Please either cancel this request and contact your support team or continue and wait for a response".

The issue in my case was that the user was using his personal Blackberry and he did NOT have an enterprise data plan (Blackberry Enterprise Plan, Blackberry Corporate Plan, BES Plan, etc. Not sure what each carrier calls it.).  He just had a regular consumer data plan called Blackberry Internet Service plan I believe.  Another clue was that the Enterprise Activation option was missing from his phone.  Even when looking in Options -> Advanced Options there was no mention of Enterprise Activation.  I found one post that recommended going into Options -> Advanced Options -> Host Routing Table and click "Register".  Once I did this, I COULD see the option for Enterprise Activation.  But that's when I ran into my error message above.

He's going to contact Verizon and upgrade his plan to a corporate plan and then I should be able to add him to the Blackberry server.