Normal? No. Unheard of? No.
Most likely your high balance got them nervous...it probably dropped your FICO about fifteen to twenty points. How long did you carry that high balance? Were you late on any other payments to anyone else during that time-frame?
The moral of the story is never max out a credit card. It drops your FICO and makes card-issuers less likely to approve CLIs. The good news is that the damage from high balances (especially if you never went over limit) is usually not lasting. Your FICO will rebound relatively quickly, and they'll probably increase your credit line again as time goes on. But this time, don't use it...