Usually for selecting out of a possibly overwhelming list I'd look into some sort of a dual list (sometimes also called list builder or accumulator). It's a user interface pattern you can see around quite often (Windows, for example, uses it to let you customize some tool bars). There are several websites to describe this pattern (can't find my old links at the moment, but here is one I just found on Google). Basically it works like this:

download bmml source – Wireframes created with Balsamiq Mockups
There is a lot of details to adjust to your needs:
There may or may not be additional filters to both the source and the selection list. The lists could be tables or icons or anything, really. Swapping items can happen instantly when clicking the entry (or as in my mockup a dedicated button), or you could mark one or more first and then swap them (see the answer by AndroidHustle). etc... etc...
Regarding your case: Your image pretty much represents the left bit of the list builder, so with regards to your task it successfully handles the selection of items. However, it does not yet provide a convenient way to keep track of what you already selected. If the filter is cleared, you can only scan the entire list of items - some checked and some not - to know who's already in the list.
The second panel in a dual list approach does this job for you: It keeps track of what's selected and keeps this choice visible and editable at all times. Additionally, it quite clearly responds to user action by moving items around, so each click has feedback. In an approach with check-boxes and changing views (by filtering) some users might be unsure about whether checking the box will commit their choice so that it lasts after the view change or if they have to press an additional button to commit. The label of the button to accept all the changes and quit the dialog must not be confused with something that suggests to save the changes in the current view state (such as "OK" or "Accept").
Overall, as you mentioned a constraint in screen estate, you have to consider the trade-off: Obviously, the list builder takes up more space. In this case, André (the answer currently above) provided a suitable approach to incorporate as much of the second panels functionality (e.g. making the existing selection available and editable) without needing additional space. You can also consider other ways to achieve this effect: If the selected list is not expected to be long you could append it below/above or you could slide in the list on clicking some show/expand button. Alternatively, you might go for a select-with-tokens approach, similar to picking e-mail recipients.
Just remember the old mantra: You need to look at how the user goes about this selection process. In the language of most design-patter descriptions:
Look into the dual list pattern when:
- what you already selected affects what you want to select next, so you need to compare what you already got to your available options. (In my opinion, the killer criterion to go for dual lists.)
- users need to adjust the selected items in some way (order or group them) on the fly
- users need to frequently revise their choice of items and hence deselect items.
Go for a single panel (with some added mechanism to quickly see the selected list) when:
- there is not much space
- what is already selected is not important for the next step, e.g. users know quite well what they want to select beforehand
- the selection does not need to be revised much
In total, you should also consider to a) add a cancel option to your suggestion to get out of the dialog without manually unchecking all the options and b) clarify what "back to view all" does (does it go back to the previous screen or does it clear the filter?)
Hope this helps. Cheers, Louise