I don't know how efficient it would be, but I usually think that most applications have a small, fixed set of possible priorities, like ("low", "medium", "high") or ("info", "warning", "error", "fatal"). In this sort of situation my initial inclination would be to implement a dict of Queue instances which corresponds to the fixed set of priorities, something like:
If priority queues were to be included, I'd rather add the necessary support in Queue to easily attach priority handling, if that's not already possible. Maybe adding a generic **kw parameter, and passing it to _put() could help a bit.
The applications of a priority Queue I've used until now weren't able to use your approach. OTOH, there are many cases where you're right, and we could benefit from this.
If it's of common sense that priority queues are that useful, we should probably add one or two subclasses of Queue in the Queue module (one with your approach and one with the more generic one). Otherwise, subclassing Queue is already easy enough, IMO (adding the **kw suggestion would avoid overloading put(), and seems reasonable to me).