The provided statistics stream is corrupt, when running UPDATE Statistics When running
    UPDATE STATISTICS mytable

I'm getting following error:
The provided statistics stream is corrupt.

When our application is inserting rows to mytable we are getting the same error.

However 
DBCC CHECKDB
Doesn't give any errors.

Any ideas on how to fix this issue?

We are running Microsoft SQL Server Express Edition with Advanced Services 2008 R2
It's a bug.  You need CU11 for Server 2008 R2 SP2
http://support.microsoft.com/kb/2829845

VSTS bug #: 1790001
FIX: &quot;The provided statistics stream is corrupt&quot; when you run the
&quot;UPDATE STATISTICS&quot; statement against a table in SQL Server 2008 R2 or
SQL Server 2012