My specific case here is that the user can pass in a string into the application, the application parses it and assigns it to structured objects.  Sometimes the user may type in something invalid.  For example, their input may describe a person but they may say their age is "apple".  Correct behavior in that case is roll back the transaction and to tell the user an error occurred and they'll have to try again.  There may be a requirement to report on every error we can find in the input, not just the first.  

In this case, I argued we should throw an exception.  He disagreed, saying, "Exceptions should be exceptional:  It's expected that the user may input invalid data, so this isn't an exceptional case"  I didn't really know how to argue that point, because by definition of the word, he seems to be right.  

But, it's my understanding that this is why Exceptions were invented in the first place.  It used to be you had to inspect the result to see if an error occurred.  If you failed to check, bad things could happen without you noticing.  

Without exceptions every level of the stack needs to check the result of the methods they call and if a programmer forgets to check in one of these levels, the code could accidentally proceed and save invalid data (for example).  Seems more error prone that way.  

Anyway, feel free to correct anything I've said here.  My main question is if someone says Exceptions should be exceptional, how do I know if my case is exceptional?

Exceptions were invented to help make error handling easier with less code clutter.  You should use them in cases when they make error handling easier with less code clutter.  This "exceptions only for exceptional circumstances" business stems from a time when exception handling was deemed an unacceptable performance hit.  That's no longer the case in the vast majority of code, but people still spout the rule without remembering the reason behind it.

Especially in Java, which is maybe the most exception-loving language ever conceived, you shouldn't feel bad about using exceptions when it simplifies your code.  In fact, Java's own Integer class doesn't have a means to check if a string is a valid integer without potentially throwing a NumberFormatException.

Also, although you can't rely just on UI validation, keep in mind if your UI is designed properly, such as using a spinner for entering short numerical values, then a non-numerical value making it into the back end truly would be an exceptional condition.
