We consider a Kondo impurity coupled to a fermionic host with a power-law density of states near the Fermi level, ρ(∈) ∼ |∈|^r, with exponent r < 0. Using both perturbative renormalization group (poor man's scaling) and numerical renormalization group methods, we analyze the phase diagram of this model for ferromagnetic and antiferromagnetic Kondo coupling. Both sectors display non-trivial behavior with several stable phases separated by continuous transitions. In particular, on the ferromagnetic side there is a stable intermediate-coupling fixed point with universal properties corresponding to a fractional ground-state spin.