I'm just creating a new list for a new client and I manually added his email address to the list but then deleted it.
This posting implies that manually deleted emails do not appear on the suppression list.
What's happening is the deleted email address is not on that client's suppression list but when I try and re-add it I'm getting this message "No recipients were successfully added, as 1 is deleted from your list, leaving a total of 1 recipients in this list".
How can I add him back onto the list?
By deleting that subscriber you've affectively suppressed him from that list. What you can do is go to the manage lists page and display all manually deleted subscribers (it's an option in the small drop down about half way down) and then check the box next to his address and at the bottom click the button to move that address back to the active list.