I've just recently finished my second playthrough of Mass Effect on Hardcore 
I'm played an Infiltrator class that I imported from my first playthrough, I used Kaidan and Wrex for the majority of the game as follows: 
I did 25+ Mission with Kaidan and Wrex (expect for Noveria where I switched out Kaidan for Liara) 
and 50+ Assignments with Kaidan and Wrex (other then the Noveria Assignments and Garrus's sidequest) (Including Bring Down the Sky - I was unable to complete Pinnacle Station on Hardcore)
 I went from level 46-59 at the end of the playthrough, and yet after doing nearly all of the assignments and all of the main mission I did not unlock either respective achievement for Wrex nor Kaidan - the Mass Effect Wiki states that the Majority of the game (which is what the achievement states "complete the majority of the game with x party member) consists of 15 Missions and 35 Assignments, I complete quite a bit over those numbers. 
 
So is this a known bug as I was quite disappointed to not receive these achievements.  
Has anyone had the same problem?

Yes, they are bugged. Same thing happened to me. I've gotten other ally achievements, and I know where everything is, and I did absolutely everything with Kaiden and Wrex, and never unlocked the achievements for either of them.

Quite a bummer I was hoping to obtain an S rank for Mass Effect, well what can you do about it - its still a fantastic game otherwise. 
This was my second playthrough, the last time I finished the game was in late 07, I had forgotten how amazing of a game Mass Effect was, the ending stretch is really something, I cannot wait to play some Mass Effect 2

It must be some sort of bug, because I snagged both the Kaiden and Wrex achievements on my first try without any trouble.  I did pretty much every side-quest available before doing story missions and I got them both around the same time on Noveria.  I've never heard of this bug, so I'm not sure how to go about fixing it, but it certainly isn't anything that is universal.

Yea I'm not sure how to "fix it" either. I have never gotten any ally achievement on either playthroughs (well taken that I probably was not using the same people regularly on my first playthrough since I did not really know what I was doing). 
 
I'm glad they got rid of these types of achievements for the second game, it allows you to play with WHO you want to play with not forcing you to play with specific characters to get achievements.

It's not a bug I don't think. You just have to make sure you do all of the side quests, even the boring planet missions.

I did every single mission in the game, I could not find anymore. I even checked on the Mass Effect Wiki and did every quest they listed, and I still did not get the Achievement. I only switched out my crew for a couple of "assignments" (sidemissions) on noveria and Garrus's sidequest, and Noveria's "Mission" (main quest). So like I said that's 25+ missions with the same characters and 50+ assignments with the same characters.