Now that I've played around with some more tags, I think the "you must have at least 2000 reputation" message shows up if you normally would have to have your edit reviewed by someone else and there is already an edit for that tag pending in the queue. If there is no edit pending, you get the normal page for entering a suggested edit and your edit is placed in the queue.
I suspect this because yesterday there were some tags where I couldn't enter suggested edits and others where I could (which wouldn't make sense if the queue was full). Now that some more edits have been approved, I see the tags I couldn't enter anything on have gained a description from someone else and the ones where I could have suggested an edit are still blank.
So it's not the size of the queue so much as the tag you were trying to edit has a pending edit already.
As an example: Yesterday, I linked to word-choice in my comment as an example of a tag I couldn't edit, and at the same time the colloquial wiki page brought me to the normal page where you can propose an edit. Today, the word-choice tag has gained a description while colloquial is still blank.
Edit: Yep, confirmation that a pending edit can prevents you from suggesting an edit (in addition to the queue being full).