Up till a couple of months ago I would have written this in VBScript no sweat but these days I am writing everything in PowerShell to get my skills up. Thanks for the challenge.
# Make 100 test files (create dir structure first)
1..100 | % ($_){New-Item "c:\scripts\Lfiles\L$_.txt" -type file}
# Rename all files to specification (remove -whatif switch to make it live)
Get-ChildItem c:\scripts\Lfiles | % ($_){rename-item -path $_.fullname -newname (($_.basename -replace "[0-9]", "")+("{0:000}" -f [int]($_.basename -replace "[^0-9]", ""))+($_.extension)) -whatif}