using Guid as PK with EF4 Code First

Have you set Identity StoreGeneratedPattern?
You can do it in the OnModelCreating method:

modelBuilder.Entity<Foo>().Property(o => o.Id).HasDatabaseGeneratedOption(DatabaseGeneratedOption.Identity);

or using the DataAnnotation attributes:

public class Foo {
  [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
  public Guid Id {get;set;}
  public string Name {get;set;}
}