The room is about 40'x20', with probably a 12'-15' ceiling. The bass and kick would most likely be miked, but the rest of the kit normally isn't.
If you're running bass and kick through the system then you probably want subs.
You didn't mention whether you actually run the bass direct but the fact that you are apparently miking it for a 40'x20' room suggests that you may be looking for some serious output for that size space and/or dealing with pretty high stage levels.
I'm looking at an entire sound system, i.e. speakers, mixer, possibly some wireless, etc... After talking with some of my superiors, we may be able to increase the budget a bit, but the more bang for our buck, the better.
'Bang for the buck' can be an interesting concept as what is perceived as 'bang' can differ. Some will focus on the bells and whistles possibly at the expense of longevity and reliability, others will do the opposite and prefer to keep it simple but reliable. Some go quantity over quality, others can do without some things initially in order to have a better foundation to work from. Some may have an extensive list of items or functionality that are 'must haves' and thus need to trade off quality to stay within budget, others may have a limited number of fixed requirements and a lot more flexibility in what is included or the related quality and costs.
Probably one of the first things to do is to consider all the ancillary items involved in a complete system. Things like DI boxes, cables and adapters, mic and speaker stands, power cords, speaker covers, a rack for the mic receivers and other gear, a stand or rack for the mixer, cases or something to store and transport the mics and cables and so on. You'd likely also want some processing or at least EQ for the monitors and mains. These are not necessarily big dollar items individually but they can add up. You might want to look at the "Quick & Dirty Bar Rig" summary here,
http://www.bennettprescott.com/. There are items listed in that summary where you would probably change the models and/or quantities or perhaps not even need and other items, such as wireless mics, that you would have to add, but it may provide some basis for putting together a comprehensive system package. What you might find is that with a limited budget accounting for all the little things that are necessary may significantly impact the money you have for the major items.
Probably one other detail to verify is whether this is a portable or installed system. When you initially said this was a "new sound system for our youth band, which currently meets in our fellowship hall", I assumed it to be a portable system that you would potentially use elsewhere as well, but if it is instaed an installed system for the Fellowship Hall then that could have its own considerations to address.