Just an update. We found out that the machine that did not have the issue was running silverlight 2, and the machine with the issue has silverlight 3. We 'upgraded' to silverlight 3 on the machine that was working, and the problem appeared.
We are still cutting down our sample, but we will have to post it to you through the support page. We won't be able to post it on the forum.