Plugin - Update step fails

I am new to CRM 2011 and working with Plug-ins. I have created a Plugin for an Entity A with two steps "Create" and "Update". Entity A has a lookup attribute to Entity B. When I am creating new record of Entity A, based on some logic I am also creating new record of Entity B if it does not exist. This works great.

I am having problem during update. When I try to update Entity A and I need to create a new record of Entity B, I get an error saying "No object matched the query: Update [Entity B]...". It looks like instead of creating a new record it is firing an Update query. Can someone please help me understand why is this happening?

To add new record I am using these statements:

context.AddObject(Entity B);

context.SaveChanges();

Thank you!