I have seen code that used to be able to send a Tweet from an Arduino, but I'm not sure if the library still works or whether it supports Push Notification style reception of Tweets.
So although this would be a really neat solution, i.e no external devices, I'd say it would a risky thing to spend time on.
Using your phone to receive the tweets sounds a better suggestion. Could you get the phone to make a sound e.g. though the headphones as well as vibrate, I guess this depends on the twitter client you are using, or what type of phone you have etc, i.e iPhone or Android.
If you can output sound if you get a tweet, it would be dead easy to feed that sound either into a digital input on the Arduino to trigger an interrupt or into an analogue input where you'd need to constantly poll the analogue input looking for variations in the input voltage.
If there aren't any twitter clients that make a sound as well as vibrate, you could look around for an open source twitter client that you could modify (e.g. possibly https://code.google.com/p/twimight/
), either to make a sound, or send data via bluetooth to the Arduino.
So just finding a twitter client that makes noises though the headphones connection is probably your best bet.