Try exporting the list and seeing what dispositions it has for the numbers.
This is just a guess, but are you based outside of North America and using a Spreadsheet to "tidy up" your lists, by any chance? If so, the problem is probably number formatting. All phone numbers in most countries begin with a zero, but Excel (et al.) see the phone number as a number and strip off the leading zero, This invalidates the numbers. When you try to trigger the campaign, it then processes it VERY fast, marking each number as being in error and therefore marking it uncallable. Within a short space of time, you have no records with callable numbers and....
Of course, the issue might be something else, but I'd start with exporting the list and looking at the dispositions...