I'd choose a blue colour of some kind. It's difficult to be more precise whith such a small photograph. How bright is the room and what kind of light does it get?

You could try a light (but not to pastel-y) yellow, tan, or light grey. Our living room is a light yellow, Valspar Spun Honey, and I love it. Plus it looks good with pretty much every color.

Not yellow. I'd paint most of the room neutral with something reddish brown on the brick wall. Or pick up one of the accent colors on the fireplace for that wall and painter a lighter version of it on the other walls. With your green furnishings I would avoid too bright or dark colors as they'll compete.

I think a light gray would look really great. If you pick a warm tone it will look wonderful with your floors and fireplace and it is neutral enough to go with the green.

Have a look at this color:
http://www.younghouselove.com/2011/01/workin-nine-to-um-nine/

I would definitely tone it down with a very pale, neutral grey/beige - something along the lines of Balboa Mist by Benjamin Moore. Keep all baseboards/woodwork white.

If you are daring, that fireplace would look smashing painted white!

Accessorize with different shades of green - chartreuse, forest green, teal, etc to tie back to your existing furniture.

Add natural elements like a sisal rug to tie back into the neutral wall color.

See that indigo blue on your countertop tilework?

That, or a shade lighter, would be a great color and go with your brown floors, brick red fireplace and green sofas...
...just make sure that everything else in the space is in one of those 4 colors or white to remain cohesive.

Whatever you do - don't select a green as they don't mix well.

You've got to decide what you want to showcase. The green sofa/tile and brick red are complimentary colors that can be a good foundation. I would probably do something more neutral on the walls and add some interest with your accents. This room could handle some pattern. Your best bet, find something with some pattern-rug, drapes, pillows, art--whatever and go from there. Whatever neutral background is in any of those would be a good place to go with wall color. How dark you want to go depends on sun exposure and what you decide to do on the floor. I have good luck with Benjamin Moore Historical colors. Just be prepared to do some serious priming because that yellow will be tough to cover.

I think that Canyon Echo by Glidden would look lovely. It's a warm grey but a very light grey. I searched for the perfect grey for months and that's what I finally settled on. You can see it in the photos here...I'd say the bottom photo is the most true:

http://operation-paper-cut.blogspot.com/2011/01/living-room-switcheroo.html

Anyway, I think this color would work because of the warm undertones- it wouldn't compete with the floor or fireplace.

Although, if you chose the right pale blue, it would look lovely, too.

I would try to avoid colors with green undertones, which most greys seem to have.

I'd also avoid anything too bold- you have a lot of richness already and I think that anything dark or saturated would be chaos.

Good luck!

second the vote for warm gray. green walls and green furniture doesn't sound good and indigo blue walls with green furniture sounds awful. If you like green furniture and a calm, soothing interior, I think a warm gray will be up your alley... then you can add pops of orange and red in pillows/throws/lamps and bring a little spunk in.

I'd dry wall/skim that ceiling too if you can afford it.

tan or a caramel coffee color comes to mind

I'd to a medium to light gray, one with orange in it so it's a warm gray.

Most paint brands put little color scheme booklets out on display with their color swatches. I suggest you try to look through some of those. Find the color of your furniture in them and see what other colors are in that group with it...

(My husband and I did this after we bought our house last August. Our couch is white, but our armchairs are a pale greenish-blue color...)

Young House Love has a Foolproof Paint and Color Scheme post that might help.
http://www.younghouselove.com/2009/06/email-answer-picking-the-perfect-paint-color/

I'd go for a cadet blue, but maybe a lighter version depending on what kind of light you get in the room. I think it would contrast nicely with the brick in the fireplace.

Farrow and Ball Light Gray or Mouse's Back. Both are great backdrop colors. and will tie your brick and floors together nicely.

Don't crap when you see the price of the paint. It's the thickness of pudding because it has so much pigment in it - totally worth it - I promise!

I vote for a cream color; you've got strong greens, warm wood floors and a brick fireplace; I would pick some warm neutral color (not yellow and not gray) for the walls.

Go with a warm mid-range tan that complements the brick. The tan will give you the richness you need, without adding another color. It will act as a neutral base and unify the other colors: brick, black, blue, white, green, wood, etc. I also agree with the suggestion to look at the Benjamin Moore Historical line, since both the architecture and your taste lean toward traditional.

I caution against light gray, or ANY light color. The brick fireplace is fairly heavy and dark. Your wall color needs a certain level of intensity in order to balance that. If the walls are pale, the fireplace will stick out like a sore thumb and feel like a dark, heavy behemoth.

I second an olive green or even a chocolatey brown or charcoal grey.

I am a broken record, but I love Monticello Rose, Benjamin Moore Historical Color 63. It is the original color Thomas Jefferson used at Monticello, and was discovered under 22 layers of paint during the 200th year restoration.

It is a wonderful color that seems to change in different sunlight. Jefferson formulated it to compliment the beautiful dark wood in his house, and it looks great with red brick, also prevalent at Monticello.

Rose is considered the most soothing of colors, and it so restive. I'm on my fourth dwelling with the color.

If that doesn't sound good, do you have a painting that you will be hanging in the room? It's an old decorator's trick to find a piece of art, and pull all the colors in the room from that piece, usually two major colors, and two minor.

I strongly third the olive color suggestion. AT just did a post on olive and you can see in the fourth picture how well other dark greens work with it: http://www.apartmenttherapy.com/ny/olive-green-interiors-136403?image_id=2124384

If you decide to paint the fireplace white, I'd suggest a slightly warmish light blue or green color like Behr's Caribbean Blue or Peridot would make the wood floors pop. (If you do go this particular brand, do yourself a favor and get the "premium plus ultra." It's more expensive, but it's been a one-coat-wonder ;) Good luck!

If it's in your budget/fits in with the style of your home and decor, wainscoting would look great in that room. Then you could go with a darker color for the wall like: Ralph Lauren Olive Tree or Khaki. If you put a shelf style mantel (it looks like there are maybe some supports for one on the fireplace?—it's hard to tell from the photo) and painted it the same color as the wainscoting trim, the fireplace will look more incorporated into the room. Or you could do two bookshelf/cabinets on either side of it going all the way up to the ceiling. Otherwise I would go more neutral like Benjamin Moore Aura: Interlude or Terra Bella—it has a little green in it. It won't go along with the blue tile work in the foreground of this photo but I wouldn't try and coordinate with that anyway. I'm assuming that it's part of your kitchen. Unless you want to extend the blue and white theme. AT has some great posts centered around that color scheme.

http://www.apartmenttherapy.com/dc/roundup/black-white-a-touch-of-blue-130011

Not sure how your green couch will tie in with that but here are a few rooms that mix in green, blue and white for inspiration.

http://mypeartreehouse.blogspot.com/2010/09/green-sofa-for-spring.html

WOW! thank you so much everybody for all the kind advice! We are both so giddy with excitement now to try out all the possibilities! So, consensus are towards warm greys/BM Historical line..

We might have to change our dark hardwood now - leakage over the weekend no thanks to seller's contractors, but perhaps it'll turn out for the better. Will surely update AT when room is ready! Thanks again!

A larger photo and more than one picture is really needed to make a decision on color.

Wheat/cream/yellow-y beige will be a nice warm neutral and it will work well with all the other stuff you have going on in there..

Or, if you have a lot of art to hang, white walls would look great against the warmth and texture of that fireplace and the hardwood floors.

I agree with a light gray with beige or olive undertones. Also remove those 3 white shelves (they are way too high.) Also, if you are not placing a dining table underneath the chandelier, then I would replace the light with something that is flush with the ceiling then add some nice table lamps or task lighting.