The method + in IndexedSeq is used to produce a new sequence containing one additional given element but you want to produce one containing an additional sequence. The method for this is ++ thus your last line must look like this:

(n.take(pivot) :+ n(successor)) ++
  ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse

You are seeing this strange compiler message about a String being expected because +'s signature does not match and thus an explicit conversion used for String concatenation kicks in (this conversion is there because it lets you write something like List(8) + " Test").

EDIT: Generalization over sequence types of ordered elements:

As I said in the comments, generalization over sequences is a bit more complicated. In addition to your element type A you will need another type CC[X] <: SeqLike[X,CC[X]] that represents the sequence. Normally C <: SeqLike[A,C] would be sufficient but the type inferencer does not like that one (you would always need to pass the types of A and C when calling that method).

If you just change your signature that way the compiler will complain that it requires an implicit CanBuildFrom[CC[A],A,CC[A]] parameter as that one is needed e.g. by the reverse method. That parameter is used to build one sequence type from another one - just search the site to see some examples of how it is used by the collections API.

The final result would look like this:

import collection.SeqLike
import collection.generic.CanBuildFrom

def nextPermutation[A, CC[X] <: SeqLike[X,CC[X]]](n: CC[A])(
  implicit ord: Ordering[A], bf: CanBuildFrom[CC[A],A,CC[A]]): CC[A] = {

  import ord._
  // call toSeq to avoid having to require an implicit CanBuildFrom for (A,A)
  val pivot = n.toSeq.zip(n.tail.toSeq).lastIndexWhere{
    case (first, second) => first < second
  }

  if (pivot < 0) {
    n.reverse
  }
  else {
    val successor = n.lastIndexWhere{_ > n(pivot)}
    (n.take(pivot) :+ n(successor)) ++
    ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse
  }
}

This way you get a Vector[Int] if you passed one to the method and a List[Double] if you passed that to the method. So what about Strings? Those are not actual sequences but they can be implicitly converted into a Seq[Char]. It is possible alter the definition of that method expect some type that can be implicitly converted into a Seq[A] but then again type inference would not work reliably - or at least I could not make it work reliably. As a simple workaround you could define an additional method for Strings:

def nextPermutation(s: String): String =
  nextPermutation[Char,Seq](s.toSeq).mkString