Gabriel does a great job explaining the default activity planning model on this thread (http://k2underground.com/forums/thread/20262.aspx).  I've extracted the pertinent part here:

 "The default creation style for an activity in BP has changed from a 'plan per destination' to 'plan once'. I assume for this reason the ActivityInstanceDestination if not available. I've not confirmed this, but try the following to see if my suspicion is right. When on the destination rule, click back and then select 'Advanced wizard view'. On the Activity planning page, select 'Plan per destination - all at once'. This will force the workflow server to create an activity destination instance for each destination and put each activity instance in the context of the destination(s). Note: You have to be aware of the result of planning per destination. For high performance systems where multiple users participate in an activity (i.e. call center style queuing), the performance impact of planning per destination should be considered"

I am having the same problem.  However, I have followed the suggestions/instructions provided and it is not having any affect.  My process worked fine until a couple of days ago, and now I my process fails at the destination rule for the first activity -- I haven't touched the destination rule at all, and the destination user hasn't changed either.  I am stumped.  If anyone has any further suggestions I am all ears.  I had similar problems in K2.NET 2003, and the only way I managed to fix it then was to create a new process and copy the flow diagram to the new process.  Needless to say I would rather not do that and instead find out what the problem is.

I'll post my findings/solution when I get to that point.