I think the clue is that you need to insert a Gmail account that is associated with the tablet. That means that you need to insert the same information that you entered when you setup this tablet for the first time. The fact that you can login to your Gmail account from other devices is not really relevant here, the tablet needs to know that you are the same owner and therefore needs to see the same user details.
Did you perhaps change to a different Gmail account or did you use someone elses account to setup the tablet the first time?
The only other thing I can think of is that the tablet is unable to contact the internet, but you seem to have covered that situation already. In such a case you would be inserting the correct Gmail address but the tablet is unable to contact the server to confirm this.