Hello. Last night I was installing Arch Linux when at some point, at the "Set Filesystem Mountpoints" stage, a message came in saying I needed a boot section, and I attributed it to my 750GB HD, unaware that it would format it, besides partitioning it. Well, now I have my HD with very important data formatted and set to ext4. I installed Windows XP and R-Linux, a data recovery program that supports ext4. The thing is: when it scans for lost files, it only finds the boot ones that are already there, and all the other programs for NTFS HD data recovery don't even recognize the HD. Is the only solution to format it again as NTFS to use one of those programs? Wouldn't it be very hard to recover my data after a second format?

I don't know anything about recovering data on an EXT4; but do not, under any circumstances try and reformat it to NTFS. That will do absolutely nothing but damage the data even more than it already is.

You don't need ext4 recovery (ala R-Linux), you need NTFS data recovery in a non-NTFS partition. Seems the other tools (presumably Windoze) you tried can't deal with that combination.
Rather than reformat (which will destroy even more data), simply try changing the id designator in the partition table to 0x07. The meta-data within the partition itself will still be all wrong (for NTFS), but the software might try to scan the partition looking for data.
Normally I'd try Photorec from Linux, but in truth I've never had a lot of luck recovering NTFS.

No need to remind you to read my sigline I guess ...

Again as usual I recommend the two best programs available, in this order:

http://www.cgsecurity.org/wiki/TestDisk

http://foremost.sourceforge.net/

If I understand you, you are telling us that you reformatted all or part of a hard disk which previously contained an NTFS filesystem and data to a new EXT4 filesystem.

Sorry to tell you but you are pretty much out of luck for recovering any data that was in the sectors which now comprise the EXT4 filesystem. You certainly can recover data from other areas of the disk but you need a considerable amount of knowledge and expertise to do so.

If the data is really important you need to image the disk before you attempt to recover any remaining data. Tools like the Sleuth Kit (TSK), Helix3 and Autopsy can then be used to carve out the data sectors and reassemble any files that are recoverable. I also suggest you read Brian Carrier's book "File System Forensic Analysis."