У меня была такая же проблема. При анализе исходного кода версии 1.8 используется другой модуль, который все еще существует. Следующее работает для меня, используя Ruby 1.9, построенный из портов на FreeBSD.
require 'date/format'
require 'time'
text = "Tue Jun 28 11:58 2011"
array = Date._parse(text, false).values_at(:year, :mon, :mday, :hour, :min, :sec, :zone, :wday)
time = Time.mktime(*array)
puts time