There is a start date and end date setting on customer profile which controls the display of customers on invoices. When you add a new customer, the start date defaults to today's date.
So if you have just added a new customer (with default start date) and now trying add an invoice for the customer in a past date, you will not be able to select the customer on invoice.
Similarly if you are editing a past invoice to change the customer to a newly added one, the newly added customer will not display on the invoice screen if the invoice date is less than the start date of the customer.
Solution is simple. Edit the customer and set the start date appropriately.