I think I should mention that I found a bag a bit of time after this thread died. I can't quite remember when but I know this thread wasn't active anymore.

My girlfriend even kinda picked it out. We were at some store that sells primarily planner stuff, and they had a sale on laptop bags and stuff. There was one that pretty much fit the bill. I'll have to take a pic of it sometime. Most importantly it got the girlfriend approval.