It is clearly overbooking. The hotel sold your room to another guest at full (read 2x) rate. If you paid in advanced, you actually don't have to leave the arrival time. If your room is paid than you can check in even at 5 a.m. I would fill a complaint directly with the hotel and tried to get them pay you compensation. (normally hotels offer free nights, points or vouchers, but that's up to you if you would like to accept this) in cash (wire is OK).
Do'n't bother with Amex, they don't even care, and they take ages to do something. As tey already charged you, maybe the best way is to open a direct hotel channel, it is the quickest way! Sometimes when you publish on Tripadvisor the hotel would then quickly find a solution.
Up to you!