You know that it's Comparables coming in, so you might as well return a Comparable array. The end user can cast it back. I haven't played around with the advancements with auto-casting in Java 1.5 though, so there might be a more efficient way to do it now.
The problem with cloning is that objects aren't required to implement it. For instance, BigDecimal is a Comparable, but it doesn't implement cloning. Therefore you aren't able to clone an array of them.
Now, you could create a new array and return it full of pointers to the objects in the other array, at which point you've fulfilled the letter of the assignment. You'll be returning a new array that affect the original. The catch is that any alterations to an object in the new array will affect the old one. But your assignment kinda sucks in that you can't ensure that the array coming in contains Cloneable objects.
As for generics and casting, I'd look at
this PDF (it's small). I think you'll find Chapter 5 to have what you're looking for.
Let me know if you're still having problems.