Roman culture placed very great emphasis on a person's "public self" - that is, on an individual's place in the hierarchy of society. The Roman conception of that hierarchy made parricide a rejection of one's place in that society, and of the key values underlying it, and as such it was considered one of the most abhorrent crimes imaginable.
Family was a key component of the Roman state. Family membership defined a citizen's place in the caste system, the block (or tribe, gens) in which he voted, and often the allegiances that he held. Chief among the Roman pantheon were the lares and penates, the household gods: Vergil, in his Aeneid, makes continual references to Aeneas' devotion to his, as he saves them from the ruins of Troy and carries them across the sea to a home in a new land. The imagines (literally "likenessses" or "statues") - busts of great personages from the family's past - also had a prominent place in the household. The Romans revered tradition, the mos maiorum ("way of the elders/betters,") referring both to historical elders and to the older people in society - youth held little value; age, wisdom, and respectability were everything. Pietas - a devotion to and respect for family, among other things - was one of the most cherished Roman virtues. Clearly, "family" was the bedrock on which the Roman conception of order was based.
The key to the horror with which Romans viewed parricide was the father's place as head of the family. By law, a Roman patriarch had absolute authority over his family. Daughters were always named after their fathers, and were similarly beholden until they were married. At that time they became part of the family into which they married, unless the marriage was sine manus ("without the hand,") which left the daughter perpetually in her father's care. Sons remained under their fathers' authority as long as he lived, and could not conduct certain types of business or borrow money without their fathers' approval. Anything a son earned or inherited belonged to his father, and that father could disown his son (and thus strip him of his own inheritance) at any time, for any reason. A Roman patriarch literally held the power of life and death over his family, to the point where he was allowed to summarily execute a family member if he deemed it necessary. How real and enforceable this authority was is debatable (for example, the last father to kill his son lived in the time of Augustus, and the act provoked a great public outcry and scandal) but the fact that it existed even in theory reflects the symbolic importance of the patriarch.
Thus, it's no real surprise that killing one's father (or mother - Nero's murder of his own outshone his many other crimes) was viewed as something worse than the already-impious betrayal of one's loving flesh and blood. The murder of a parent by a child was nothing less than an attack on the key societal unit, on the entity that gave that child a place in society - and thus on society itself. Parricide was, to the Romans, a kind of treason - treason against the inviolate family, treason against the state, and treason against the natural order of the universe itself. It's not surprising, then, that the penalty was so brutal: a parricide was to be savagely beaten, then sewn into a leather sack with a dog, a cock, a viper, and an ape. The whole assembly was then cast into the nearest body of water, where the criminal would drown as his bruised flesh was torn to pieces by the panicked animals. There is some doubt as to whether this penalty was ever actually carried out (it would have involved great difficulty, for monkeys are hard to come by in Italy.) Nevertheless, it was a grave, if symbolic, statement of Roman society's view of crime's severity.
Incidentally, the historical novellist Steven Saylor deals with this issue in his novel Roman Blood, a detective story set in ancient Rome and loosely based on the writings of Cicero (one of the orator's first cases was the defense of Sextius Roscius, accused of parricide.) It's a good story and does a fine job of illustrating many of the concepts I've discussed here.
A note on "parricide" vs. "patricide" - both usually mean the murder of a father, but "parricide" can also refer to the murder of a mother or ancestor in general, while "patricide" means "father" exclusively. Thanks to Spork_Avenger for asking about this first.
Sources:
A History of Private Life, ed. Paul Veyne, trans. Arthur Goldhammer, Harvard University Press, 1987.
Corrigan, Peter, lectures on Roman Civilization, spring 1999.
Cross, Suzanne, "The World Within: Domus and Definition," from "Feminae Romanae: The Women of Ancient Rome," http://dominae.fws1.com/world_within/Index.html.
Suetonius, De Vita Caesarum, 2 vols., trans. J. C. Rolfe (Cambridge, Mass.: Harvard University Press, 1920), pp. 123-287. Scanned by: J. S. Arkenberg, Dept. of History, Cal. State Fullerton, as part of the Internet Ancient History Sourcebook, http://www.fordham.edu/halsall.