Try disabling reset on the mega with 10uF cap between reset and ground after uploading Arduino as ISP to it.
The fact that the same mega with same connections works for nick's board programmer implies that the connections are fine; but the issue with needing to disable autoreset does impact some people (for reasons unclear, not everyone).