Patients receive veliparib orally (PO) twice daily (BID) on days 1-14 (days 0-13 of course 1 only). Patients also receive cisplatin intravenously (IV) over 1 hour on day 1 and vinorelbine ditartrate IV over 10-20 minutes on days 1 and 8. Treatment repeats every 21 days for 6-10 courses in the absence of disease progression or unacceptable toxicity. Treatment with veliparib alone may continue in the absence of disease progression or unacceptable toxicity.