A convex loss function that has a minimum guarantees that there is a minimum loss that can be reached by going "downhill" from whatever point you're at. So your supervised learning algorithm, which is typically trying to minimize some loss function, will (unless something goes wrong) be able to find the "best" result, where "best" is relative to the specified loss function. Without convexity, you might have multiple local minima, and your algorithm can find one which is, local minimum though it may be, nonetheless very poor relative to the global minimum.
Edit: As mbq points out in comments, some algorithms will still be able to find global minima (under certain conditions), but many algorithms are local optimizers that use convexity assumptions because it makes finding a minimum a lot simpler.
Nonlinear classification is important because it greatly expands the possibilities for good classification rules. Linear rules imply that everything on one side of a straight line (plane in multiple dimensions) gets one classification, everything on the other gets the other (if there are two classes.) Nonlinear rules allow much more flexibility, e.g., everything inside a circle gets one classification, everything outside gets another. Of course, you can mimic a nonlinear classification rule by transforming your inputs to a linear classification rule appropriately, but what is appropriate? Much better to have an algorithm in effect figure that out for you, more or less, than have to guess, and guess, and guess again - unless of course you already have a good idea.