Here's another bit that might help you. The Irish Times has an ancestor surname search. If you go to http://www.irishtimes.com/ancestor/index.htm and enter your family's surname, it will turn up the areas where that last name was most common in the mid-1800s. You might have trouble if you're looking for a really common Irish surname like Murphy, but a quick search on Sullivan shows that most were living in County Cork or County Kerry. You'll have to pay a charge of 7 Euros if you want it broken down by parish, but you can probably find that information elsewhere.

A good site I found for Irish Genealogy is The Irish Genealogy Tool Kit (http://www.irish-genealogy-toolkit.com/index.html) Lots of helpful hints and informative accompanying blog.