Could it be just that I need to give it some time for apple to remove the old email from the system?
That is possible, but waiting more than a couple of hours isn't likely to change anything.
Without knowing the particular email address you wish to use though, it is difficult for me to speculate regarding the reason it is not available. Please do not reveal that email address (or any other) on this website (or any other). I do not want that information and knowing it could not help anyway.
To pursue fixing the problem on your own, you can try typing that email address into this web page: Recover Your Apple ID - Apple. A useful result would be "<...> is not an Apple ID". If it is an Apple ID, the next page will ask you how you would like recover your password or security questions. The outcome would be helpful information, so let me know what you determine.
Otherwise, you will need to ask Apple for assistance with your Apple ID: Contact Support, Select a product (doesn't matter which), and then select Apple ID & Password. Proceed from there.