Not sure there is a solution to this problem with Linq to Sql. If you are using Sql Server 2005 you could define a (recursive like) Stored Procecdure that uses common table expressions to get the result that you want and then execute that using DataContext.ExecuteQuery.
Maybe you could try taking a step back and seeing what you want to do with the relation? I'm assuming you want to display this information to the user in e.g. "modified by Iain Galloway 8 hours ago".
Could something like the following work? :-
var users = from u in db.Users
select new
{
/* other stuff... */
AddedTimestamp = u.AddedTimestamp,
AddedDescription = u.AddedByUser.FullName,
ChangedTimestamp = u.ChangedTimestamp,
ChangedDescription = u.ChangedByUser.FullName
};
I've used an anonymous type there for (imo) clarity. You could add those properties to your User type if you preferred.
As for your second question, your normal LoadWith(x => x.AddedByUser) etc. should work just fine - although I tend to prefer storing the description string directly in the database - you've got a trade-off between your description updating when ChangedByUser.FullName changes and having to do something complicated and possibly counterintuitive if the ChangedByUser gets deleted (e.g. ON DELETE CASCADE, or dealing with a null ChangedByUser in your code).
Any type of cycles just aren't allowed. Since the LoadWith<T> or AssociateWith<T> are applied to every type on the context, there's no internal way to prevent an endless loop. More accurately, it's just confused on how to create the SQL since SQL Server doesn't have CONNECT BY and CTEs are really past what Linq can generate automatically with the provided framework.
The best option available to you is to manually do the 1 level join down to the user table for both of the children and an anonymous type to return them. Sorry it's not a clean/easy solution, but it's really all that's available thus far with Linq.