I've been using LuaInterface and Lua 5.1 in several C# applications that required scripting, most notably a few games, an IRC bot and a full IRC client that I've recently decided to resume working on.
At one point, I switched to .Net 4.0 and had to recompile LuaInterface and Lua51 just to get them to run again. As far as I could tell, all was good.
However, I recently bought a new laptop and tried to run my bot from it. To my surprise it broke when it tried to initialize Lua, citing a FileNotFoundException on lua51.dll, which was sitting right there. I shrugged it off for later and continued reinstalling things, including Visual C# and C++ 2010 Express, and some updates. The next morning I tried starting the chatbot again to try and figure it out -- lo and behold, it worked. For some strange reason.
Earlier today, a friend of mine told me to finish the IRC client I was working on, which makes rather extensive use of Lua to add functions and other cool stuff. I gave said friend a copy to check out for the most important problems... and he got the exact same error.
Now, the other guy does not have Visual Studio, I can't reproduce the problem, and one can't expect users of the other things I listed above to install it just to get them running -- the average relatively sane user would just shrug and get rid of the program.
So what do, SO?
citing a FileNotFoundException on lua51.dll, which was sitting right there
Which makes it likely that it complained about not finding a DLL that lua51.dll needs. A very likely one is msvcr100.dll, the C/C++ runtime support library. Which does get installed when you install Visual Studio. You can rebuild lua with the /MT option so the CRT is included in the DLL itself. Or tell your friend to download and install this.