I am using Cxx.jl on Mac OSX 10.9.5 (64 bit). Cxx requires Julia v0.4.0-dev (i.e., staged functions). I have rebuilt Cxx many times and the only trouble I encountered was due to not updating Clang in deps/llvm-svn and related directories.
I think it is best to file an issue in Cxx.jl and hopefully someone can help you with linux-specific issues.
