This really is a bummer, you have my complete sympathy. I know how harsh this outcome seems, when I was applying I had to make a similar decision about the 'denied entry, deported' clause, and when you're faced with it, it feels like telling the truth is going to cause your application to be rejected; you convince yourself that you weren't 'really' deported, or 'arrested' (as the other person in this thread did), and sometimes a visa refusal is as simple as not getting a long-term visa and going as a tourist instead, so you forget about the initial refusal. For us, having a lawyer who could simply say 'put it down, they don't care' saved a potential disaster. They should put out a fact sheet with a few common scenarios on it (visa-on-arrival denied, etc. etc.).
And it also seems harsh, to me, that the appeal is a totally technical process, not something where you can present evidence of an imbalance between intent (in this case, bad legal advice) and results (total destruction of future plans and current life); but that's the difference between justice and administration. If it were different, processing of applications would never end; but sometimes that end really causes unnecessary damage. The fact that it's not CIC's fault doesn't, at least for me, change the basic sadness in this outcome.