We need to fix hosting. period. Once hosting is fixed people like myself (and maybe some others) will actually take the time to recruit other people.
Me and Burnt spent like $500 in advertising a few years ago. It worked. There were at least 100 new users who logged on over the course of 2-3 weeks. We saw an average of like 20-30 additional players logged on at any given time during that advertising period... But we quickly lost them(and others along the way) simply because people need to have the ability to host games.