A resposta fornecida por @marc_s na questão é a maneira de fazê-lo.
No seu caso ficaria assim:
create table Users
(
Id int identity (3000, 1),
UserId as '08U1'+right('0000'+cast(Id as varchar(5)), 5) persisted,
UserName varchar(50),
LastName varchar(50),
Location varchar(50),
constraint PK_Users primary key (UserId)
)
Eu não faria como sugerido aqui . Você terá duplicatas se excluir uma linha ou em caso de simultaneidade.
SQL Fiddle
