I tried adding both DataColumns first, then the tooltips. Turns out it had to be in this order:
data.addColumn('number', 'y');
data.addColumn('number', 'Line 1');
data.addColumn({type: 'string', role: 'tooltip'});
data.addColumn('number', 'Line 2');
data.addColumn({type: 'string', role: 'tooltip'});
instead of
data.addColumn('number', 'y');
data.addColumn('number', 'Line 1');
data.addColumn('number', 'Line 2');
data.addColumn({type: 'string', role: 'tooltip'});
data.addColumn({type: 'string', role: 'tooltip'});
Updated working fiddle: http://jsfiddle.net/Qquse/1207/