New Brunswick is nice, and if you are into old buildings, or people, it's probably pretty cool, but it's the least interesting to me of all the provinces up there. St. Andrews is quite pretty but there's not a lot going on.

Personally I'd skip Nova Scotia and New Brunswick in general and spend 5 nights in Cape Breton. You will not be dissapointed wtih Cape Breton.