How far are yopu prepared to go with this? You have a confirmation email stating room booked ok, you have proof of a deposit being debited and you have a mail from the hotel (in advance of stay) stating the room is not available due to overbooking.
Fair enough go ahead and push for your room or an upgrade but don't just arrive on the day and expect magic.
As for the legal side I'm not too sure where you stand.
BTW, did anyone hear Morning Ireland this morning - I think it was the business news, a company in Limerick had devised a system whereby hotels can now update their room availability and prices in real time. This system would have prevented the problem the OP now has.