Use CustomValidator
This control (written by me) supports CheckBox and CheckBoxList:
http://www.codeproject.com/KB/validation/AtLeastOneOfValidator.aspx
Just add it to visual studio, drop it on your page, and add your checkboxes to it's Controls list. It will work like any other validator control.
Worst case you can write a CustomValidator the can do whatever you like. Sounds like what you need is along the lines of:
isValid = Check1.Checked | Check2.Checked
Custom validator is the obvious solution. Also, when using a custom validator you should also check for validity on the server side just in case the javascript fails due to some reason.
P.S.: Don't always trust what the client(browser) sends you.
Here is an article I wrote regarding this exact issue. I also wanted to validate multiple controls which was easy using the CustomValidator but one of the issues I was not happy about is that if you corrected the validation issue the error did not go away until you posted back.
I figured out a way to hide the error message and revalidate and wrote a small blog entry about it. Check it out and see what you think.