It is indeed hard to press two atoms together once their electrons have begun to overlap significantly. However a lot of solids have free space within them i.e. their density is lower than it would be if they were close packed spheres. This means you can compress those solids by forcing their atoms to rearrange.
For example, the density of diamond is about 3.5g/cc while graphite is about 2.2 g/cc. That means there's a lot more free space in graphite so it's probably easier to compress i.e. it has a lower bulk modulus. As Manishearth has commented, the spacing between the graphite layers is relatively large so I expect it to be easiest to compress in this direction. However from a quick Google I couldn't find bulk modulus values for the two forms.
In principle if you compress graphite enough it would rearrange into diamond. I don't think anyone has managed this in a controlled way. Synthetic diamonds are grown under pressure, but I think this involves dissolution in molten metal to speed the process.