After correspondence with the package maintainer, I found out that the most recent commit was not pushed to github yet. This issue is now resolved and installing from github works flawlessly:
install_github("kasperdanielhansen/Rgraphviz")
The problem was caused by some agressive compiler settings used on Ubuntu 12.04.
It was solved in commit e0e2b6dcd1cc09b14d150889a83780c978e1cc37.