I guess since shoes are two, that's why it's nuevo"s"? I thought since they're a pair, it would be singular. Is that true for other pairs too? Pair of jeans, pair of glasses, pair of earrings, socks etc.?
Usually, yes, though there are lots of other little rules as well. This is usually a good resource, http://www.studyspanish.com/lessons/serest1.htm but I have to say, this time I can't figure out why it's ser and not estar, I just used ser without thinking about it.