The correlations are negative because as one variable increases the other tends to decrease:
As the variable on the x-axis changes from 1 to 2 to 3, the one on the y-axis changes from 3 to 2-and-3 to 1-and-2 ... clearly as one increases
the other is tending to decrease. Hence negative correlation measures.
The nominal measures of association don't have a negative value because they treat the categories as unordered. There's no "direction" to call positive or negative, so values are only more associated or less associated (closer to independent).
You didn't say whether your categories are ordered, so it's not even possible to suggest which might be relevant.
[Now that it's clear that both variables are ordered, neither Phi nor Cramer's V are particularly useful. In spite of the the claim that Pearson's R is for interval-interval association, it could be used here (since the difference between using the original category-scores and the average ranks is not that large), as could the Spearman correlation. I would perhaps lean toward Kendall's tau-b, but it really depends on why you're doing this and what you're hoping to find out.
However, I'd advise you not to even look at a measure if you don't know what it does or why it's relevant (better not to even calculate it if you don't know it's meaningful for your analysis).
It's would be much better to understand what you're trying to achieve and choose your analysis than dump it into some program that blindly calculates dozens of (mostly irrelevant) quantities and then leaves you to pick out what you want. It's direct enticement to data-dredging (conscious or unconscious).
Try to have a goal in mind -- a question or questions you want to address (that is, what you want to find out from your data), and focus your attention toward answering those questions. Exploratory data analysis is fun, no doubt about that, and it can help you to understand your tools, but for it to make sense you need to at least have made some investigation of what those things are and whether they are sensible things to use on your data.
The Wikipedia pages on all of these quantities aren't terrible, so perhaps start with those to get a sense of what they're doing and what they tell you.