As you have mentioned, your users are currently complaining on the road to a new major version.
Isn't it expected that due to a major version bump the API may change?
Either you don't make backwards-incompatible changes in the API, or you would be doing that in a major version bump. If you aren't doing it in a major version bump, where would you be doing that? Unless you do it in a minor version bump, which is obviously even more improper. So basically, there is nowhere better to do it apart from a major version bump, right?
API changes are or are not expected in a major version change, depending on your system of API versioning. It seems that in your case, it is. This is your own decision, although common. Unless you are totally not planning to make backwards-incompatible changes.
Is it "uncommon" to change the API in a beta phase?
The beta phase, according to the usage specified in your post, can be assumed as "previews of a release candidate", and "not finalized". If you are having backwards-incompatible changes, you should release them as soon as possible in order to give more time to the users of your API, say, to fix the compatibility problems. Of course, you won't do that in releases before the version bump because of obvious reasons (you have already marked
@Deprecated in earlier versions! Why did people still compile code despite the warnings?). Since you are going to make these changes in the release candidate anyway, why leave them later? Moreover, technically your beta versions are already major-version-bumped.
This question can also be understood as API changes betwteen beta releases of the same version. As long as you are going to add these changes in the major version bump, it is not a problem. After all, during the beta phase, the API changes can be considered as "not yet finished changing".
Finally, always remember: every single change breaks backwards compatibility.
xkcd: Workflow -- There are probably children out there holding down spacebar to stay warm in the winter! YOUR UPDATE MURDERS CHILDREN.