I ended up replacing the link in the :before block like Edgard suggested:
<div id="parent">
<%= link_to_remote "Click Here",
{:url => "/some_long_url",
:method => :post,
:before => "$('#parent').html('#{escape_javascript(link_to("Click Here"))}');"} %>
</div>
Note this uses JQuery. If you're using prototype you might need to change the '.html' method to the prototype equivalent ('.update' I believe).
Then after the AJAX call is made it redraws the link_to_remote with something like...
render :update do |page|
page.replace_html 'parent', :partial => 'partial_containing_your_link_to_remote', :locals => {}
end
The link_to_remote in the first part should really be in that same partial to keep it DRY