str_replace is great for replacements but you have a pattern to find and section of that pattern you want to reuse. In your example, you insert the ENTIRE original string back into each link. YOu also lose the name for description of the link.
A regular expression does the job when your needs are more complicated:
$txt="The quick brown #fox jumps over the lazy #dog.";
$try2 = preg_replace('/#([A-Za-z][A-Za-z0-9]+)\b/i','<a href="/user.php?u=$1">$1</a>', $txt);
A quick explanation of this regular expression in case you aren't very familiar with them: /#([A-Za-z][A-Za-z0-9]+)\b/i Find the # sign followed immediately by a letter followed immediately by 1 or more letters or numbers. Stop selecting the pattern when we reach a word boundary (\b). The first and last '/' slashes are delimiters. The 'i' at the end means to search without regard to upper or lower case.
The portion in parentheses will be held onto as a reference. That reference ($1) in our case can then be used twice in the replace for the query-string parameter and link text. (Think of copy and paste. $1 is the first entry in the virtual clipboard.)
* This regular expression could be refined a bit but I'm going with this one for readability purposes.
It worked for me using php 5.3 with the test string I included in the sample. By default preg_replace() replaces all matches unless a limit is set. It doesn't search for the @at sign as that wasn't presented in your original example. For the @ sign change the regex to this: /\b[#@]([A-Za-z][A-Za-z0-9]+)\b/i Your expression would also, basically work if you remove the '^', which means "starts with". That expression explicitly says the string must begin with an @ to match.
The one I wrote also insists that the first character to follow the # or @ must be a letter. That way a string like, "You're #1" won't match.
NOTE: I added a \b in front of the expression to prevent a match on an email address.
* I'm not at my home computer right now, so I haven't tested the expressions in this posting.