I only ever caught a Feebas once, and I couldn't ever remember where the spot was. I was lucky: I got a female, so have been breeding it like crazy, though I've no one to trabe feebas with...
Hatch feebas, and see what Nature it is. If it's anything other than the ones listed by the others, forget trying to evolve it and go for another egg. Then grow berries like Wiki, Pamtre, chesto, and blend them to get indigo and blue pokeblocks. I've found Wiki's are best ( others may disagree ;) ) as higher the level, the more the attribute is raised. If you're blending berries of more than one flavour, go for ones which are dry, or have dry as part of the mix. Blend your berries, then feed your feebas with the blue blocks with both high level and low feel. High level advances the attribute more, but a low feel block will allow your pokemon to eat more. Saying that, if you feed any pokemon with two high level blocks, they'll get full. That's why I go for Wiki Berries.
Once you've filled the feebas with blocks, look at it's condition chart. The green section should touch the blue segment in the Beauty corner, and preferably, actually touch the outline of the pentagon. As a final check, take your feebas to see the Pokemon Fanclub Chairman: if Feebas has a high enough Beauty, s/he'll get a blue scarf.
I then suggest giving your feebas an exp. share, and battling to level it up. I think I too tried a rare candy once, and had the same result you did: no evolution. Try leveling up a couple of levels, as sometimes the Feebas needs to have a slightly higher level to evolve.
If, however, this doesn't work, then I'm sorry, but it sounds like your game has a glitch, and you'll have to find someone to trade with ;)