I personally witnessed the latter happening in Starcraft 2; a section of the achievements would have you win hundreds of games against their AI opponents (boring!)
That presupposes that you're actually trying to get that achievement. Most people that get this achievement play AI matches in order to practice and get better at the game.
Your overall question really depends on what you want achievements to do. They can have many functions, and not all achievements need to do the same things.
Design Feedback
It is really important to understand this: achievements were invented for game designers, not players. Oh, they have useful psychological effects, but they're really just tools for knowing what someone is doing with the game.
Take Civilization V's Steam Achievements. There are a number of achievements that are basically, "Beat the game with character X." By monitoring these achievements, Civ V's developers can know which characters are popular and which are not.
That's why a lot of games have achievements that are basically, "Got this far in the game." They're used to tell how far players progress on average. If you find that most of your players stop 30% of the way through the game, you may want to check to see what happened between your 30% achievement and your 50% achievement.
Not all of your achievements should be for game design achievements. But some certainly should be.
Grinding Rewards
Like the StarCraft II example you gave, sometimes you just want to give players an award for doing something that isn't itself particularly interesting. This shows how dedicated the player in question is at mastering the game. For a game like SC2, these could be considered rights of passage along your progress as a skilled player.
These generally don't encourage grinding. They're rewards, not encouragement. It's a way of saying, "You played our game a lot. Here you go." Some OCD players may actively try to achieve them, but that's not what they're for. They don't really encourage replay; they reward replay that you would have done anyway.
Behavior Encouragement
This one is mostly for multiplayer games. It can have positive and negative consequences, depending on how well you design them.
Team Fortress 2 has quite a few achievements that reward playing in a certain way. Some of them work well. An achievement for backstabbing a certain number of characters helps to encourage proper play of the Spy class. Some don't, such as the one that encourages Medics to stop doing their job and go attack people with their pathetic weapons, leaving their teammates to die and lose the match!
So... yeah. Make sure that if you're trying to encourage behavior, you don't promote negative or abborant behavior. Behavior achievements should encourage play that helps the game.
These generally don't help the replay value. They're there mainly to point the user in the right way of playing the game, and reward them for doing so.
Challenge Rewards
Challenge rewards are essentially you giving the player something to strive to. They should be difficult to achieve.
These do promote replay value, depending on the kind of challenge. However, it only promotes replay among players who like the particular challenge in question. You need to design these with a firm understanding of what is easy and what is hard in your game. Also, you need to know what is possible in the game. And most of all, what your players will find enjoyable.
Civ V's set of achievements has quite a few of these. The most famous of which is probably the One City Challenge.
Accidental Awards
These are mostly failed Challenge Rewards. The developers thought something might be a challenge, but the circumstances that might bring it about are either completely out of the player's control, or so unlikely to work that the only way it would happen is by dumb luck.
So when making Challenge Rewards, make sure not to go so far that the player really has no control of when they would even get the chance to pull it off.
Awesomeness Rewards
A particular intersection of "Behavior Encouragment" and "Challenge Rewards." These recognize that there is some particularly difficult but cool that someone could do. You want people to try it, and you want to reward them for pulling it off.
Not all Challenge rewards require awesome behavior. But Awesomeness Rewards are probably the most coveted kind, because getting them is both hard and awesome.
A great example is the TF2 achievement "Be Efficient" A Sniper kills 3 people without missing a shot. It's hard to make that happen, but when you finally pull it off, you feel like a boss.
Again, you have the potential issue of encouraging improper behavior. So you make sure that the awesome thing is something that benefits the team and doesn't work against good play.
Consolation Prizes
The consolation prize is an achievement given because the player screwed up. A lot. It's not designed to encourage behavior, since the behavior it would "encourage" already has plenty of negative stigma on it (like for example, dying a lot). It's mostly a way to point out that fail happened. To you.
Obviously, these don't encourage replay value.
