You could be a hard-gainer because you exercise TOO much.
I'm also a hard-gainer, but have now found a pretty good balance. I eat about 2500 calories per day, crank out 150 or 200 pushups in the morning, and do a lot of walking. Every now and then I'll throw in some pullups and a sprint or two. And I'm just as muscular now as I ever was before - and that's when I was doing squats, deadlifts, bench-press, etc.
I'd recommend limiting your workouts to strength training 3 times per week - MWF - using either StrongLifts or Rippetoe's Starting Strength. Continue to eat the same amount, and I bet you begin seeing weight gain right away.
Ditch the running, and anything else that doesn't focus in on your main goal of gaining weight and strength.